15. 三数之和

题目链接：15. 三数之和

方法：排序 + 相向双指针

解题思路

• 由题意可知，排序不影响结果，非递减排序之后3数之和满足单调性，即\(x < x1\) || \(y < y1\) || \(z < z1\)，\(f(x, y, z) < f(x1, y1, z1)\)；
• 现在枚举\(x\)下标\(0 <= i <= n - 2\)，在\([x + 1, n - 1]\)中选择\(y\), \(z\)的下标\(l\), \(r\)，初始化\(l = x + 1，r = n - 1\)；
  （1）若\(nums[i] > 0\)，则后续没有\(f(x, y, z) == 0\);
  （2）若\(nums[i] == nums[i - 1]\)，跳过此次循环，去除重复的数对，因为\(x = i，l = x + 1, r = n - 1\)的满足条件的三元组在\(x = i - 1, l = x + 1, r = n - 1\)中已经计算过了；
  （3）计算\(sum = f(x, y, z)\)：
  • \(sum < 0\)，由于\(r\)此时已经是最大值，故 \(l ++\)；
  • \(sum > 0\)，同上，\(r --\) ；
  • \(sum == 0\)，将\({nums[i], nums[l], nums[r]}\)加入返回数组，此时若\(nums[l] == nums[l + 1]\)，会出现重复数对，故 \(l ++\) ，直到\(nums[l] != nums[l + 1]\)，对于右端点同理，若\(nums[r] == nums[r - 1]\)，则 \(r --\) ，直到\(nums[r] != nums[r - 1]\)。

代码

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

复杂度分析

时间复杂度：\(O(n^2)\)；
空间复杂度：\(O(1)\)。