牛客網：三數之和

 

目錄

方法一：暴力

方法二：雙指針

---

方法一：暴力

三重循環應該大家都能想到

但是這個過不了啊

怎麼辦呢，就利用一個O(nlogn)複雜度的排序來降低一下複雜度，怎麼降低呢？排序之後相同元素會在一起，我們遇到相同的直接跳過就行了。

代碼如下所示：

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;
    }
};

方法二：雙指針

我們可以利用雙指針的方法把時間複雜度降到O(n^2)，首先還是排序，因為這可以讓我們跳過重複元素。其次這也方便我們使用雙指針。

接下來對數組中的數進行如下處理：

1.設置後面兩個數的指針，即後面區域的左右指針

• 如果三個數相加等於0，則將三個數放入答案，然後更新兩個指針至不重複元素比特置
• 如果大於0，將右指針往左移一比特
• 如果小於0，將左指針往右移一比特

退出的條件就是當左指針的比特置>=右指針的比特置時

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;
    }
};