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

分析：

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

一、一层循环+双指针

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(),nums.end());vector<vector<int>> ans;for(int i=0;i<nums.size()-2;++i){if(nums[i]>0) break;if(i>0&&nums[i]==nums[i-1]) continue;int right=nums.size()-1;int target=-nums[i];for(int left=i+1;left<right;++left){if(left>i+1&&nums[left]==nums[left-1]) continue;while(left<right&&nums[left]+nums[right]>target) --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<vector<int>> &ans ,int &a,int & b,int &c){vector<int> temp={a,b,c};sort(temp.begin(),temp.end());ans.insert(temp);return;}vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(),nums.end());set<vector<int>> ans;unordered_map<int,int> hash;for(int i=0;i<nums.size();++i){if(hash.find(nums[i])==hash.end()){hash[nums[i]]=1;}else{hash[nums[i]]+=1;}}for(int i=0;i<nums.size()-2;++i){if(nums[i]>0) break;if(i>0&&nums[i]==nums[i-1]) continue;for(int j=i+1;j<nums.size()-1;++j){if(j>i+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<vector<int>> 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<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(),nums.end());vector<vector<int>> res;for(int i=0;i<nums.size()-2;i++){if(nums[i]>0) break;//减少不必要的判断if(i>0 && nums[i]==nums[i-1]){continue;}unordered_set<int> Set;//每次创建一个Set，用完这次销毁。int target=-nums[i];for(int j=i+1;j<nums.size();j++){int temp=target-nums[j];if(Set.find(temp)!=Set.end()){res.push_back({nums[i],nums[j],temp});while(j<nums.size()-1&&nums[j]==nums[j+1]) ++j;}else{//else 非必要。此时nums[j]可以被存，因为temp<nums[j]，因此nums[j]在后面永远不会被再次考虑，存了也不影响结果Set.insert(nums[j]);}}}return res;}
};