三数之和：排序加双指针去重

目标是在数组中找到所有和为 0 且不重复的三元组。暴力枚举需要 $O(n^3)$ ；排序后固定一个数，可将后两数搜索降为线性。

思路#

排序后枚举 i。在区间 [i + 1, n - 1] 中维护 left、right：和太小就右移 left，和太大就左移 right，恰好为零时记录答案并跳过重复值。

1
class Solution {
2
public:
3
    vector<vector<int>> threeSum(vector<int>& nums) {
4
        int n = nums.size();
5
        vector<vector<int>> res;
6

7
        if(n == 3) {
8
            int x = nums[0] + nums[1] + nums[2];
9
            if(!x) {
10
                res.push_back(nums);
11
                return res;
12
            }
13
            else {};
14
        }
15

16
        sort(nums.begin(), nums.end());
17
        for(int i = 0; i < n - 2; i ++ ) {
18
            if(i > 0 && nums[i] == nums[i - 1]) continue;
19
            int x = -nums[i];
20

21
            int l = i + 1, r = n - 1;
22
            while(l < r) {
23
                int t = nums[l] + nums[r];
24

25
                if(t == x) {
26
                    res.push_back({-x, nums[l], nums[r]});
27
                    while(l < r && nums[l] == nums[l + 1]) l ++;
28
                    while(l < r && nums[r] == nums[r - 1]) r --;
29
                    l ++, r --;
30
                }
31
                else if(t > x) r --;
32
                else l ++;
33
            }
34
        }
35

36
        return res;
37
    }
38
};

易错点#

去重不只发生在 i：找到答案后，左右指针也必须越过相同元素，否则会重复收集同一三元组。时间复杂度为 $O(n^2)$ ，排序以外只使用常数额外空间。