分析

要判断是否存在：

• 三元组 [nums[i], nums[j], nums[k]] ；
• 满足 i != j、i != k 且 j != k ；
• 满足 nums[i] + nums[j] + nums[k] == 0 。

请你返回所有和为 0 且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

我们的第一想法可能是直接暴力，但是直接暴力时间复杂度高达$O(n^3)$。

这里我们采用排序 + 双指针的做法。

题解

排序 + 双指针

排序后面对相同的数，我们可以跳过，因为核心是判断 nums[i] + nums[j] + nums[k] == 0，我们通过确定第一个数，然后使用双指针去寻找满足要求的另外两个数。

时间复杂度：$(O(n\log n)+O(n\cdot n) = \boldsymbol{O(n^2)})$

定义指针：

• l: i + 1左指针，指向区间范围最小的数；
• r: n - 1右指针，指向区间范围最大的数。

为什么左边界是l = i + 1?

约定下标顺序：$\boldsymbol{i < l < r}$

• $i$ 是我们外层循环固定的第一个数；
• $l$ 必须在 $i$ 的后面，不能等于、不能在前面；

如果 $l \le r$ ：

1. 会出现下标重复，（ $(l = i)$ 同一个元素用两次，违反题意，每个元素只能使用一次）；
2. 同一个三元组会被多次搜索到，比如三元组 $(1, 2, 3)$ ，$i = 1, i = 2$ 时都会搜到，产生重复答案。

因此左指针只能从 $i + 1$ 起步。

为什么右边界是r = n - 1?

n - 1是数组最后一个元素下标，是整个数组最右端。

我们的目标：在 $i$ 右侧这片区间 $[i+1, n-1]$里，找两个数相加等于-nums[i]。

双指针规则：

• l从左往右走（数变大）
• r从右往左走（数变小）

想要拥有最大的收缩空间，右指针一开始必须放在区间最末尾也就是n - 1。

指针如何移动？

sum = nums[i] + nums[l] + nums[r]

1. 当sum > 0，和太大，需要减小数字，右指针r左移；
2. 当sum < 0，和太小，需要增大数字，左指针l右移；
3. 当sum = 0，左右指针都要跳过此时指针指向的相同数字，然后l++, r--指向下一个数字。

代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < n; i++) {
            if(i && nums[i] == nums[i - 1]) continue;
            int l = i + 1, r = n - 1;
            while(l < r) {
                int sum = nums[l] + nums[r] + nums[i];
                if(sum > 0) r--;
                else if(sum < 0) l++;
                else {
                    res.push_back({nums[l], nums[r], nums[i]});
                    while(l < r && nums[l] == nums[l + 1]) l++;
                    while(l < r && nums[r] == nums[r - 1]) r--;
                    l++;
                    r--;
                }
            }
        }
        return res;
    }
};

15. 三数之和 - 力扣（LeetCode）