题目:
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
解:这道题一开始的解法如下，讲其分为查找两数之和的子问题，但测试用例再最后两个用例上显示超时
class Solution1 { public: vector<vector<int>> threeSum(vector<int>& nums) { std::sort(nums.begin(),nums.end()); vector<vector<int>> v2; set<vector<int>>set_v2; int i=0; if(nums.size()<=2) { return v2; } for (;i<nums.size()-2;i++) { int tmp_1=nums[i]; int j=i+1; map<int,int> tmp_map; //unordered_map<int,int> tmp_map;
for(;j<nums.size();j++) { vector<int> vec_3; int tmp_2=-tmp_1-nums[j]; if(tmp_map.find(tmp_2)!=tmp_map.end()) { vec_3.push_back(tmp_1); vec_3.push_back(tmp_2); vec_3.push_back(nums[j]); sort(vec_3.begin(),vec_3.end()); if(set_v2.find(vec_3)==set_v2.end()) { set_v2.insert(vec_3); v2.push_back(vec_3); } } tmp_map[nums[j]]=j; } } return v2; } };
测试可得unordered_map的时间比map快一倍，unordered_map为4s，map为7s。且将tmp_map[nums[j]]=j;这行注释后，时间缩短为1s
可得插入时间比较费时
以上的时间复杂度计算为O(n2),但未计算map插入的时间复杂度，可能应该为O(n2*logn)
下面为双指针方法，时间复杂度O(N2),所有测试用例通过
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { //排序的作用在于去掉重复的数字 std::sort(nums.begin(),nums.end()); vector<vector<int>> v2; int i=0; //异常处理 if(nums.size()<=2) { return v2; } for (;i<nums.size();i++) { //大于0就不用往下走 if(nums[i]>0) { break; } if(i>0&&nums[i-1]==nums[i]) { continue; } int i_left=i+1; int i_right=nums.size()-1; while(i_left<i_right) { if(nums[i]+nums[i_left]+nums[i_right]==0) { v2.emplace_back(std::vector<int>({nums[i],nums[i_left],nums[i_right]})); //寻找接下来满足条件的 //首先跳过重复的 while(i_left<i_right &&nums[i_left]==nums[i_left+1]) i_left++; while(i_left<i_right &&nums[i_right]==nums[i_right-1]) i_right--; i_left++; i_right--; } else if(nums[i]+nums[i_left]+nums[i_right]>0) { i_right--; } else i_left++; } } return v2; } };
关于双指针方法，双指针的使用 一般要先进行排序
下面是别人对其进行的总结
https://www.cnblogs.com/codingstory/p/11334827.html
