题解 | #数组中相加和为0的三元组#

题意思路：
找出三个数相加为0的组合，即a+b+c=0，题目输出为三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）。
方法一：暴力法

首先最朴素的做法是先排序然后通过三重循环寻找答案,可以优化如果循环的当前数和之前一样则continue，可以卡过本题数据。

时间复杂度：O(nlogn) +O(n^3);排序算法O(nlogn)+三重循环枚举

空间复杂度：O(n);数组存储与读取数据

 class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int>>ans;
        if(num.size()<3)return ans;
        sort(num.begin(),num.end());//排序使最后结果满足非降序排列
        for(int i=0;i<num.size()-2;i++){
            if(i&&num[i]==num[i-1])continue;//如果循环的当前数和之前一样则continue
            for(int j=i+1;j<num.size();j++){//不重复选择当前数加1
                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){
                        ans.push_back({num[i],num[j],num[k]});//最后输入按非降序排列
                    }
                }
            }
        }
        return ans;
    }
};

方法二：双指针优化

具体思路：

我们在用朴素算法暴力解决问题时，通过挖掘某些性质，使得算法时间复杂度由 O(n^3)->O(n^2) 。

我们进行循环选择第一个数x，然后创建两个指针i和j，指针i指向下一个数，指针j指向最后一个数。

若指针i 加指针j 大于当前数 x则指针j --，

若指针i 加指针j 小于当前数 x则指针i++，

若指针i 加指针j 等于当前数x 则答案为x 和指针i 与j 的三元组。

时间复杂度：O(nlogn) + O(n^2)；排序算法O(nlogn)+双指针

空间复杂度：O(n);数组存储与读取数据

下图演示了双指针算法过程：

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int>>ans;
        if(num.size()<3)return ans;
        sort(num.begin(),num.end());
        for(int i=0;i<num.size()-2;i++){
            if(num[i]==num[i-1]&&i)continue;
            int l=i+1,r=num.size()-1;
            while(l<r){
                if(num[l]+num[r]==-num[i]){//若指针i 加指针j 等于当前数x 则答案为x 和指针i 与j 的三元组。

                    ans.push_back({num[i],num[l],num[r]});
                    while(num[l]==num[l+1]&&l+1<r)l++;
                    while(num[r]==num[r-1]&&r-1>l)r--;
                    l++,r--;
                }
                else if(num[l]+num[r]>-num[i]){//若指针l 加指针r 大于当前数-num[i]则指针r --，
                    r--;
                }
                else l++;//若指针l 加指针r 小于当前数-num[i]则指针l++，
            }
        }
        return ans;
    }
};