力扣hot100：15.三数之和（双指针/哈希表）

分���：

        三数和问题，这里和两数之和不一样，返回的是值，因此可以对其进行排序，使用双指针。

一、一层循环+双指针

class Solution {public:    vector threeSum(vector& nums) {        sort(nums.begin(),nums.end());        vector ans;        for(int i=0;i0) break;            if(i>0&&nums[i]==nums[i-1]) continue;            int right=nums.size()-1;            int target=-nums[i];            for(int left=i+1;lefti+1&&nums[left]==nums[left-1]) continue;                while(lefttarget) --right;                if(left!=right)                    if(nums[left]+nums[right]==target) ans.push_back({nums[i],nums[left],nums[right]});            }        }        return ans;    }};

二、一层循环+扫一遍的哈希表

为了避免第一层循环不必要的重复值，需要进行排序。

无脑往集合里塞，然后使用集合去重。（由于是全局的哈希表，因此（i,j）和(j,i)都会被放入，会有重复）。

这里的基本思路是，塞入的时候只需要看数量多少即可，比如3+3+3=9，那是否真正存在3 个3呢，只有两个3是不行的。

时间复杂度：O（n²+klogk+3klog3）

class Solution {public:    void Insert(set &ans ,int &a,int & b,int &c){        vector temp={a,b,c};        sort(temp.begin(),temp.end());        ans.insert(temp);        return;    }    vector threeSum(vector& nums) {        sort(nums.begin(),nums.end());        set ans;        unordered_map hash;        for(int i=0;i0&&nums[i]==nums[i-1]) continue;            for(int j=i+1;ji+1&&nums[j]==nums[j-1]) continue;                int cur=-nums[i]-nums[j];                if(hash.find(cur)!=hash.end()){                    if(cur==nums[i]||cur==nums[j]){                        if(nums[i]==nums[j]){                            if(hash[nums[i]]>2) Insert(ans,nums[i],nums[j],cur);                        }else{                            if(cur==nums[i]){                                if(hash[nums[i]]>1) Insert(ans,nums[i],nums[j],cur);                            }else{                                if(hash[nums[j]]>1) Insert(ans,nums[i],nums[j],cur);                            }                        }                    }else Insert(ans,nums[i],nums[j],cur);                }            }        }        vector result;        for(auto it=ans.begin();it!=ans.end();++it){            result.emplace_back(*it);        }        return result;    }};

三、一层循环+问一遍

对比一下：力扣hot100：1.两数之和-CSDN博客

这里问一遍的开销更大了，因为每次问都得重开一个集合。清空集合或销毁集合一共O(K)（K是不同元素的个数）。（两数和只需要一个集合，没常数级别的判断所以更快）

而扫一遍却只需要一个集合，用常数级别判断。
思路：

        第一层循环确定一个数i，第二层循环 从之后的数开始 从前往后遍历，每次遍历时如果这个数j 和 之前存入集合的数 可以构成一个可行解，则将结果保存起来，并且这个情况下，这个数j和它对应的另外一个数 对于数i而言都不能再出现在结果中，不然会存在重复（确定两个另外一个必然唯一确定）。因此当这个数j被存入结果中时，下次我们既要 从 与这个数不同的数 开始考虑（避免选定同样的两个数），也不需要把这个数j存入集合（可以存但无意义，之和不会再考虑它）。

清空set，而不是销毁set（Set.clear()），速度更快：

class Solution {public:    vector threeSum(vector& nums) {        sort(nums.begin(),nums.end());        vector res;        for(int i=0;i0) break;//减少不必要的判断            if(i>0 && nums[i]==nums[i-1]){continue;}            unordered_set Set;//每次创建一个Set，用完这次销毁。            int target=-nums[i];            for(int j=i+1;j