题目：
TLE做法（哈希+两重for循环）
标签虽然说是用双指针，但是第一个想法真就不是双指针呀。。。就感觉这道题很像：
力扣hot1--哈希-CSDN博客
于是就用了类似的想法：
- 首先要排个序，至于为什么要排序，是为了好对三元组集合去重。
- 接下来与力扣hot1的想法一样，用哈希来存储一遍这些元素，但是有的元素可能重复了好多次（注意这里数组已经排过序了），所以unordered_map<int,vector<int>>，vector<int>记录对应的索引。
- 用双重for循环来判断，第三个数是否在哈希表中，如果存在，还要判断索引是不是一致，如果一致，那就还是不行。如果不一致，那就记录下来，存入res。为了方便去重，这里采用了顺序存取三个数。
- 最后用set去重啦，虽然TLE了，但是。。。记录一下代码（以下是TLE的代码）
代码：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
//nums排序
sort(nums.begin(),nums.end());
//哈希存
vector<vector<int>> res;
unordered_map<int,vector<int>> hmap;
int len=nums.size();
for(int i=0;i<len;i++){
hmap[nums[i]].push_back(i);
}
//两重for循环遍历
for(int i=0;i<len-1;i++){
for(int j=i+1;j<len;j++){
//cout<<"i:"<<i<<' '<<"j:"<<j<<endl;
//cout<<"nums_i:"<<nums[i]<<' '<<"nums_j:"<<nums[j]<<endl;
auto iter=hmap.find(0-nums[i]-nums[j]);
if(iter!=hmap.end()){
auto p=iter->second;
int p_len=p.size();
for(int k=0;k<p_len;k++){
if(p[k]!=i && p[k]!=j){
int temp=iter->first;
//cout<<"i:"<<nums[i]<<" j:"<<nums[j]<<" temp:"<<temp<<endl;
if(temp<=nums[i]){res.push_back({temp,nums[i],nums[j]});}
else if(temp>=nums[j]){res.push_back({nums[i],nums[j],temp});}
else{res.push_back({nums[i],temp,nums[j]});}
break;
}
}
}
}
}
//set去重
set<vector<int>> q(res.begin(),res.end());
res.assign(q.begin(),q.end());
return res;
}
};这里记录一下set去重：
//set去重
set<vector<int>> q(res.begin(),res.end());
res.assign(q.begin(),q.end());C++ 给vector去重的三种方法_c++ vector去重-CSDN博客
单循环+双指针做法
言归正传，双指针思路：
- 首先，先给数组排个序。为什么要排序呢，有点像二分的思想。这里可以先大致感受一下，L 指针在最左面，R 指针在最右面，满足三个数之和等于0，那就添加结果。小于0就说明 L 指针指的数有点小了，往右侧移动。大于0就说明 R 指针指的数有点大了，往左侧移动。
- 排完序后，依次遍历数组中的每个元素，就代表三个元素之和已经降维成了两个元素之和，或许可以想到哈希表的做法（为什么双指针也很方便呢？因为这道题不是返回索引，可以进行排序），后面将尝试哈希表的做法~
- 如果说遍历到的元素索引为 i ，那么 L = i +1，R = nums.size( ) - 1。然后进行第一段的说法，也就是：
while(L<len && R>=0 && L<R){ if(nums[i]+nums[L]+nums[R]==0){ res.push_back({nums[i],nums[L],nums[R]}); while(L<R && nums[L+1]==nums[L] && L+1<len){L++;} while(L<R && nums[R-1]==nums[R] && R-1>=0){R--;} L++;R--; } else if(nums[i]+nums[L]+nums[R]<0){L++;} else{R--;} }
代码如下：
C++：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> res;
int len=nums.size();
for(int i=0;i<len;i++){
if(nums[i]>0){break;}
if(i>0 && nums[i]==nums[i-1]){continue;}
int L=i+1;
int R=len-1;
while(L<R){
if(nums[i]+nums[L]+nums[R]==0){
res.push_back({nums[i],nums[L],nums[R]});
while(L<R && nums[L]==nums[L+1]){L++;}
while(L<R && nums[R]==nums[R-1]){R--;}
L++;
R--;
}
else if(nums[i]+nums[L]+nums[R]<0){L++;}
else{R--;}
}
}
return res;
}
};Python：
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res=[]
nums.sort()
len_nums=len(nums)
for i in range(len_nums):
if nums[i]>0:
break
if i>0 and nums[i]==nums[i-1]:
continue
L=i+1
R=len_nums-1
while L<R:
if nums[i]+nums[L]+nums[R]==0:
res.append([nums[i],nums[L],nums[R]])
while L<R and nums[L]==nums[L+1]:
L+=1
while L<R and nums[R]==nums[R-1]:
R-=1
L+=1
R-=1
elif nums[i]+nums[L]+nums[R]<0:
L+=1
else:
R-=1
return res
单循环+哈希做法
哈希思路：
数组遍历循环每一个元素，对于该元素，在该元素的右侧进行【两数之和=0-该元素】的降维处理。可参考：力扣hot1--哈希-CSDN博客
代码如下：
C++：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
int len=nums.size();
vector<vector<int>> res;
for(int i=0;i<len-2;i++){
if(nums[i]>0){break;}
if(i>0 && nums[i]==nums[i-1]){continue;}
unordered_map<int,int> hmap;
int target=-nums[i];
int temp_last=0x3f3f3f3f;
for(int j=i+1;j<len;j++){
int temp=target-nums[j];
if(hmap.find(temp)!=hmap.end()){
res.push_back({nums[i],nums[j],temp});
}
else{
hmap[nums[j]]=1;
}
}
}
set<vector<int>> s(res.begin(),res.end());
res.assign(s.begin(),s.end());
return res;
}
};
Python：
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
len_nums=len(nums)
res=[]
for i in range(len_nums-2):
if nums[i]>0:
break
if i>0 and nums[i]==nums[i-1]:
continue
hmap={}
target=-nums[i]
temp_last=0x3f3f3f3f
for j in range(i+1,len_nums):
temp=target-nums[j]
if temp in hmap:
res.append([nums[i],nums[j],temp])
else:
hmap[nums[j]]=1
s=set(tuple(x) for x in res)
res=[list(x) for x in s]
return resPython中的去重：
s=set(tuple(x) for x in res)
res=[list(x) for x in s]
