18. 四数之和

Difficulty: 中等

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] ：

  • 0 <= a, b, c, d < n
  • a、b、c 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

1
2
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

1
2
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

  • 1 <= nums.length <= 200
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109

Solution

Language: cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());//排序，保证相同的数位置相邻
        vector<vector<int>> res;
        for (int i = 0; i < nums.size(); ++i) {
            if (i && nums[i] == nums[i - 1]) continue;//遍历放在第一个位置的数，相同的数选第一个，后面的跳过
            for (int j = i + 1; j < nums.size(); ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;//遍历放在第二个位置的数，相同的数选第一个，后面的跳过
                for (int k = j + 1, u = nums.size() - 1; k < u; ++k) {
                    if (k > j + 1 && nums[k] == nums[k - 1]) continue;//遍历放在第三个位置的数，相同的数选第一个，后面的跳过
                    while (u - 1 > k && nums[i] + nums[j] >= target - nums[k] - nums[u - 1]) --u;//遍历放在第一个位置的数，要选择满足条件的最前面的数，从左往右的第一个数
                    if (nums[i] + nums[j] == target - nums[k] - nums[u]) {
                        res.push_back({nums[i], nums[j], nums[k], nums[u]});
                    }
                }
            }
        }
        return res;
    }
};

47. 全排列 II

Difficulty: 中等

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

1
2
3
4
5
输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

Solution

Language: c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<bool> used;
    int n;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());//排序，保证相同的数位置相邻
        n = nums.size();
        used = vector<bool>(n);
        path = vector<int>(n);
        dfs(0, nums);
        return res;
    }
    void dfs(int u, vector<int>& nums) {
        if (u == n) {
            res.push_back(path);
            return;
        };
        for (int i = 0; i < n; ++i) {
            if(!used[i]) {
                if (i && nums[i] == nums[i - 1] && !used[i - 1]) continue;//选择从左往右第一个未被填过的数字
                //如果used[i - 1] == false，说明第 i - 1 个数未被使用，故当前遍历的第 i 个数不是从左到右第一个未被填过的数，要跳过
                path[u] = nums[i];
                used[i] = true;
                dfs(u + 1, nums);
                used[i] = false;
            }
        }
    }
};

77. 组合

题目描述

给定两个整数 nn 和 kk，请返回从 1…n1 … n 中选 kk 个数的所有方案。

样例

1
2
3
4
5
6
7
8
9
10
输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

算法

(DFS) O(Cnk×k)O(C_n^k \times k)

深度优先搜索，每层枚举第 uu 个数选哪个，一共枚举 kk 层。由于这道题要求组合数，不考虑数的顺序，所以我们需要再记录一个值 startstart，表示当前数需要从几开始选，来保证所选的数递增。

时间复杂度分析：一共有 CnkC_n^k 个方案，另外记录每个方案时还需要 O(k)O(k) 的时间，所以时间复杂度是 O(Cnk×k)O(C_n^k \times k)。

C++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;

    vector<vector<int>> combine(int n, int k) {
        dfs(0, 1, n, k);
        return ans;
    }

    void dfs(int u, int start, int n, int k)
    {
        if (u == k)
        {
            ans.push_back(path);
            return ;
        }

        for (int i = start; i <= n; i ++ )
        {
            path.push_back(i);
            dfs(u + 1, i + 1, n, k);
            path.pop_back();
        }
    }
}; 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> combine(int n, int k) {
        dfs(n, k, 1);
        return ans;
    }
    void dfs(int n, int k, int start) {
        if (k == 0) {
            ans.push_back(path);
            return;
        }

        for (int i = start; i <= n; ++i) {
            path.push_back(i);
            dfs(n, k - 1, i + 1);
            path.pop_back();
        }
    }
};