一.题目描述
题目链接:
https://www.nowcoder.com/practice/345e2ed5f81d4017bbb8cc6055b0b711?tpId=196&&tqId=37085&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking
给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。
注意：

  • 三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）
  • 解集中不能包含重复的三元组。

例如，给定的数组 S = {-1,0,1,2,-1,-4},解集为(-1,0,1),(-1,-1,2)
二.算法(双指针)
图片说明
思考：首先我们要思考对于两个元素我们该如何处理？双指针！！这个算法肯定呼之欲出，那么对于三个元素，我们只需要确定其中一个元素对另外两个元素使用双指针是不是就可以了??
思路：
(1)首先对数组进行排序,从小到大进行排序，对后续的搜索肯定是有帮助的
(2)依次取出第i个数，从0开始不重复的选择
(3)这样问题就转换为2个数求和的问题，双指针就可以使用
(4)定义两个指针：左指针(left)和 右指针(right)
(5)找出固定 left， 此时left所指的位置为数组中最小数，再找到两个数和 不大于 target 的最大 right 的位置
(6)调整left的位置后移，求解和是否为target

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        sort(num.begin(), num.end());//开始进行从小到大进行排序
        vector<vector<int> > res;
        if (num.size() < 3) return res;//小于三个直接返回false 进行特判
        for (int i=0;i<num.size()-2;i++) {
            int j=i+1;
            int k=num.size()-1;
            int target=-num[i];//预先减去遍历元素的大小
            //双指针操作
            while (j<k) {
                if (num[j]+num[k]>target) k--;//结果大于目标值 右指针左移
                else if (num[j]+num[k]<target) j++;//结果小于目标值 左指针左移
                else {
                    vector<int> current = {num[i], num[j], num[k]};
                    res.push_back(current);
                    //都是为了防止重复
                    while (j+1<k&&num[j+1]==num[j]) j++;
                    while (k-1>j&&num[k-1]==num[k]) k--;
                    j++;
                    k--;
                }
            }
            //防止重复
            while(i+1<num.size()-2&&num[i+1]==num[i]) i++;
        }
        return res;
    }
};

时间复杂度:O(n * n)对于每一个数都遍历，所以复杂度是n * n
空间复杂度:O(n)需要额外空间来返回结果
优缺点:时间复杂度低，但是实现起来麻烦，细节点多
三.算法(暴力搜索)
开始对数组从小到大进行排序，然后利用递归+回溯+剪支很显然是可以解决了。

class Solution {
public:
    void dfs(int i,set<vector<int>> &res,vector<int> &temp,vector<int> &num,int sum,int target,vector<vector<int>> &result){
         //剪支
        if(i>=num.size()||temp.size()>3) return;
        if(temp.size()==3&&sum!=target) return;
        sum+=num[i];
        temp.push_back(num[i]);
       //边界条件
        if(temp.size()==3&&sum==target&&res.find(temp)==res.end()){
            result.push_back(temp);
            res.insert(temp);
            //return;
        }
        dfs(i+1,res,temp,num,sum,target,result);
        //回溯
        sum-=num[i];
        temp.pop_back();
        dfs(i+1,res,temp,num,sum,target,result);
    }
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int>> result;
        set<vector<int>> res;
        if(num.size()==0) return result;//对元素直接返回空二维vector
        vector<int> temp;
        sort(num.begin(),num.end());//预先对数组进行排序
        dfs(0,res,temp,num,0,0,result);//开始搜索
        return result;
    }
};

时间复杂度:O(n*n)对于每一个数字都要从开始进行一次遍历，所以复杂度为n * n
空间复杂度:O(n)需要额外空间返回最后结果
优缺点:时间复杂度高，但是实现简单