数组中和为0的三个数

1.暴力法

暴力法虽然测试用例能正确输出，但是程序时间复杂度太高直接超时，

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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            //使用双指针解决剩余两个数字
            for (int j = i + 1; j < nums.size(); ++j) {
                for (int k = j + 1; k < nums.size(); ++k) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        //判定符合要求的答案是否重复
                        //ans.push_back({nums[i], nums[j], nums[k]});
                        if (ans.size() == 0) ans.push_back({nums[i], nums[j], nums[k]});
                        else {
                            int flag = 1;
                            for (int m = 0; m < ans.size(); ++m)
                            if (ans[m][0] == nums[i] && ans[m][1] == nums[j] && ans[m][2] == nums[k]) flag = 0;
                            if (flag) ans.push_back({nums[i], nums[j], nums[k]});
                        }
                    }
                }
            }
        }
        return ans;
    }
};

2.排序+双指针

参考：https://leetcode.cn/problems/1fGaJU/solutions/1764953/by-ac_oier-6mfb/

  1. 对数组进行排序，使用三个指针 i、j 和 k 分别代表要找的三个数，
  2. 通过枚举 i 确定第一个数，另外两个指针 j，k 分别从左边 i + 1 和右边 n - 1 往中间移动，找到满足条件的所有组合。
  3. j 和 k 指针的移动逻辑，分情况讨论 sum = nums[i] + nums[j] + nums[k] ：
    • sum > 0：k 左移，使 sum 变小
    • sum < 0：j 右移，使 sum 变大
    • sum = 0：找到符合要求的答案，存起来
  4. 由于题目要求答案不能包含重复的三元组，所以在确定第一个数和第二个数的时候，要跳过数值一样的下标
  5. 在三数之和确定的情况下，确保第一个数和第二个数不会重复，即可保证三元组不重复（简化！）
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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        int len = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 0; i < len; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            //使用双指针解决剩余两个数字
            int j = i + 1, k = len - 1;
            while (j < k) {
                //限定条件一个都不能漏掉
                while (j > i + 1 && j < len && nums[j] == nums[j - 1]) j++;
                if (j >= k) break;
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    ans.push_back({nums[i], nums[j], nums[k]});
                    j++;
                } else if (sum > 0) {
                    k--;
                } else if (sum < 0) {
                    j++;
                }
            }
        }
        return ans;
    }
};