首页 > 代码库 > 3Sum

3Sum

2024-07-28 01:02:41   214人阅读

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

  • Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
  • The solution set must not contain duplicate triplets.

 

    For example, given array S = {-1 0 1 2 -1 -4},    A solution set is:    (-1, 0, 1)    (-1, -1, 2)

分析：该题的主要思路是：先对num排序，然后最外层循环从第一个元素到倒数第三个元素，循环里用2sum两个指针的解法。此题的难点在于如何remove duplicates。如果在最后对结果除重，会超时，所以要在产生的过程中防止产生重复的triplet。
class Solution {public:    vector<vector<int> > threeSum(vector<int> &num) {        vector<vector<int>> res;        int n = num.size();        if(n < 3) return res;                sort(num.begin(), num.end());        for(int i = 0; i < n-2; i++){
　　　　　　　//remove duplicates            if(i == 0 || (i > 0 && num[i-1] != num[i])){                int left = i+1, right = n-1;                while(left < right){                    if(num[i] + num[left] + num[right] < 0)                        left++;                    else if(num[i] + num[left] + num[right] > 0)                        right--;                    else{                        res.push_back({num[i], num[left], num[right]});                        left++;                        right--;
　　　　　　　　　　　　　　//remove duplicates                        while(left < right && num[left] == num[left-1])                            left++;                        while(left < right && num[right] == num[right+1])                            right--;                    }                }            }        }        return res;    }};

 

3Sum


联系
我们