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

数组中相加和为0的三元组

1、题意重述

给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。

换句话说，即从数组S中找3个数，并且这3个数相加为0.

2、思路整理

使用双指针的思想：

Step1:(首先排序，在这里排序使用快排，直接出结果即可)固定一个数，另外两个数用双指针指向。我们设l，r两个指针，分别指向固定数的后一个数和数组中的最后一个数

Step2：判断l，r指针指向数值的和与固定值的相反数进行比较。

①如果num[l] + num[r] == -num[i],返回结果

②如果num[l] + num[r] > -num[i] 则r--

③如果num[l] + num[r] < -num[i] 则l++

Step3：将固定的数往右移动，重复Step2操作，最后得出结果。

3、代码实现

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]){
                   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]){
                    r--;
                }
                else l++;
            }
        }
        return ans;
    }
};

4、复杂度分析

时间复杂度：遍历数组加双指针遍历，因此时间复杂度为$O(N^2)O(N^2)$。

空间复杂度：使用常数级内存地址空间，因此空间复杂度为$O(1)O(1)$。