15.三数之和

​题目来源：

        leetcode题目，网址：15. 三数之和 - 力扣（LeetCode）

解题思路：

        1.三重循环暴力遍历，超时原因，三重循环复杂度太高

        2.双重循环+哈希表，超时原因，哈希表无法判断是否重复，需要暴力遍历，从而导致超时

        3.双指针。固定第一个数的值，

解题代码：

//暴力遍历，超时
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;sort(nums.begin(),nums.end());if(nums[0]>0 || nums[nums.size()-1]<0){return res;}for(int i=0;i<nums.size();i++){for(int j=i+1;j<nums.size();j++){int sum2=nums[i]+nums[j];if(sum2>0){break;}for(int k=j+1;k<nums.size();k++){int sum3=nums[k]+sum2;vector<int> temp={nums[i],nums[j],nums[k]};if(sum3==0){if(res.size()!=0 && contains(res,temp)){continue;}res.push_back(temp);}}}}return res;}bool contains(vector<vector<int>>& res,vector<int> temp){for(int i=res.size()-1;i>=0;i--){if(res[i][0]!=temp[0]){break;}if(res[i][1]==temp[1] && res[i][2]==temp[2]){return true;} }return false;}
};

//双重循环+哈希表，超时
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;sort(nums.begin(),nums.end());unordered_map<int,int> map;for(int i=0;i<nums.size();i++){map[nums[i]]=map[nums[i]]+1;} for(int i=0;i<nums.size() && nums[i]<=0;i++){map[nums[i]]--;unordered_map<int,int> newMap=map;for(int j=nums.size()-1;j>i && nums[j]>=0;j--){newMap[nums[j]]--;if(newMap[-nums[i]-nums[j]]>0){vector<int> temp{nums[i],-nums[i]-nums[j],nums[j]};if(!contains(res,temp)){res.push_back(temp);}}}}return res;}bool contains(vector<vector<int>>& res,vector<int> temp){//res中是否包含tempfor(int i=res.size()-1;i>=0;i--){if(res[i][0]==temp[0] && res[i][1]==temp[1] && res[i][2]==temp[2]){return true;} }return false;}
};

//双指针
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;sort(nums.begin(),nums.end());for(int i=0;i<nums.size();i++){if(i!=0 && nums[i]==nums[i-1]){continue;}int target=0-nums[i];int left=i+1;int right=nums.size()-1;while(left<right){if(nums[left]+nums[right]==target){vector<int> temp{nums[i],nums[left],nums[right]};res.push_back(temp);left++;right--;while(left<right && nums[left]==nums[left-1]){//放在if外是需要增加 left!=(i+1)的判断，否则形如 -1,-1,2 的结果会被跳过left++;}while(left<right && nums[right]==nums[right+1]){right--;} }else if(nums[left]+nums[right]<target){left++; }else{right--; }}}return res;}
};

总结：

        没通过，看官方题解的。

---