Niuke.com: sum of three numbers

 

Catalog

Method 1 ： violence

Method 2 ： Double pointer

---

Method 1 ： violence

The triple cycle should come to mind

But this can't pass

What shall I do? , Just use one O(nlogn) Reduce the complexity by sorting the complexity , How to reduce it ？ After sorting, the same elements will be together , If we encounter the same problem, just skip it .

The code is as follows ：

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int>> res;
        if(num.size()<3) return res;
        sort(num.begin(), num.end());
        for(int i=0;i<num.size()-2;++i){
            if(i&&num[i]==num[i-1]) continue;
            for(int j=i+1;j<num.size()-1;++j){
                if(j>i+1&&num[j]==num[j-1]) continue;
                for(int k=j+1;k<num.size();++k){
                    if(k>j+1&&num[k]==num[k-1]) continue;
                    if(num[i]+num[j]+num[k]==0){
                        res.push_back({num[i],num[j],num[k]});
                    }
                }
            }
        }
        return res;
    }
};

Method 2 ： Double pointer

We can use the double pointer method to reduce the time complexity to O(n^2), Sort first , Because this allows us to skip repeating elements . Secondly, it is convenient for us to use double pointers .

Next, the numbers in the array are processed as follows ：

1. Set pointers to the next two numbers , That is, the left and right pointers of the rear area

• If three numbers add up, they are equal to 0, Put three numbers in the answer , Then update the two pointers to the non repeating element position
• If it is greater than 0, Move the right pointer one bit to the left
• If it is less than 0, Move the left pointer one bit to the right

The exit condition is the position of the left pointer >= The position of the right pointer

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