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

数组中相加和为0的三元组
给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。
注意：
三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）
解集中不能包含重复的三元组。

示例:
输入：[-10,0,10,20,-10,-40]
返回值：[[-10,-10,20],[-10,0,10]]

方法一 暴力法

使用三个for去获取序列对应的值a,b,c一样匹配，对于处理相同的答案时使用map去记录该答案是否出现过

代码

vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int> > res; //记录答案
        map<vector<int>, bool> vis; //存储出现过的答案
        sort(num.begin(), num.end()); //将序列变成有序后面方便存值
        for(int i = 0; i < num.size(); i ++)
            for(int j = i + 1; j < num.size(); j ++)
                for(int k = j + 1; k < num.size(); k ++){
                    if(num[i] + num[j] + num[k] == 0){ //当取到的值总和为0时
                        vector<int> ans({num[i], num[j], num[k]});
                        if(!vis[ans]) res.push_back(ans); //当答案第一次出现的时候讲答案记录
                        vis[ans] = 1;
                    }
                }
        return res;
    }

时间复杂度: 使用三个指针进行取值判断，以及答案的标记时间map插入与查找复杂度为
空间复杂度: map中存入的数不会达到3个一样的情况因为固定两个数能得出第三个数所以复杂度会达到

方法二 双指针

其实双指针的做法和方法一差不多方法一其实也算是使用了双指针的做法,只不过做了些优化
1.对数组num进行了排序，这样存入时就不需要进行排序直接存入即可，
2.直接找到三个元素进行计算，首先固定一个元素i对i之后的l到r元素进行遍历，
3. 如果说明符合条件就加入,说明结果小了将 反之大了将;

代码

vector<vector<int> > threeSum(vector<int> &num) {
        int n = num.size();
        sort(num.begin(), num.end()); //排序
        vector<vector<int> > ans;
        for(int i = 0; i < n; i ++){    //遍历i
            int l = i + 1, r = n - 1;
            if(i != 0 && num[i] == num[ i - 1]) continue; // 如果与前面一位相同就跳过
            while(l < n && r < n &&l < r){//双指针
                int sum = num[l] + num[r] + num[i]; //获取三元组
                if(sum == 0){    //如果合法
                    vector<int> re;
                    re.push_back(num[i]); re.push_back(num[l]); re.push_back(num[r]);
                    ans.push_back(re);
                    while(l < r && num[l] == re[1]) l ++; //去除重复l值
                    while(l < r && num[r] == re[2]) r --; //去除重复r值
                }else if(sum > 0){    //大于0说明值大了所以右指针向左移缩小sum值
                    r --;
                }else l ++; //相反
            }
        }
        return ans;
    }

时间复杂度: 复杂度会达到,每次会遍历l到r,并且遍历n遍
空间复杂度: 使用了若干个变量