三数之和
map法
数组变成map，key是数组值，value是数组下标，
之后双层循环，在map的key里面找到0-nums（j）-nums（j），再检查下标是否相同
最后对key排序，在结果里没出现就加入
#include <iostream> #include<string> #include<vector> #include<unordered_map> #include <algorithm> #include<map> using namespace std; class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { unordered_map<int, int> num_map; vector<int> sum_1; vector<vector<int>> sum; for (int i = 0; i < nums.size(); i++) { num_map.insert(pair<int, int>(nums[i], i)); } for (int i = 0; i < nums.size(); i++) { for (int j = i+1; j < nums.size(); j++) { auto iter = num_map.find(0 - nums[i] - nums[j]); if (iter != num_map.end() ) { if ((*iter).second != i && (*iter).second != j ) { sum_1.push_back(nums[i]); sum_1.push_back(nums[j]); sum_1.push_back((*iter).first); sort(sum_1.begin(), sum_1.end()); if (find(sum.begin(), sum.end(), sum_1) == sum.end()) { sum.push_back(sum_1); } sum_1 = {}; } } } } return sum; } }; int main() { Solution a; vector<int> nums = { -1,0,1,2,-1,-4 }; vector<vector<int>> sum; sum = a.threeSum( nums); for (int i = 0; i < sum.size(); i++) { for (int j = 0; j < sum[0].size(); j++) cout << sum[i][j] << " "; cout << endl; } return 0; }
双指针法
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; sort(nums.begin(), nums.end()); // 找出a + b + c = 0 // a = nums[i], b = nums[left], c = nums[right] for (int i = 0; i < nums.size(); i++) { // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了 if (nums[i] > 0) { return result; } // 错误去重a方法，将会漏掉-1,-1,2 这种情况 /* if (nums[i] == nums[i + 1]) { continue; } */ // 正确去重a方法 if (i > 0 && nums[i] == nums[i - 1]) { continue; } int left = i + 1; int right = nums.size() - 1; while (right > left) { // 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组 /* while (right > left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; */ if (nums[i] + nums[left] + nums[right] > 0) right--; else if (nums[i] + nums[left] + nums[right] < 0) left++; else { result.push_back(vector<int>{nums[i], nums[left], nums[right]}); // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重 while (right > left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; // 找到答案时，双指针同时收缩 right--; left++; } } } return result; } };
二刷
哈希法（最后超时）
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; unordered_map<int,int> my_map; sort(nums.begin(),nums.end()); for(int i=0 ; i<nums.size()-1;i++) { for(int j=i+1 ; j<nums.size();j++) { auto it= my_map.find(0 - nums[i] - nums[j]); if( it != my_map.end() ) { vector<int> tmp = { nums[it->second] , nums[i] , nums[j]}; if(find(result.begin(),result.end(),tmp) == result.end()) result.push_back(tmp); tmp.clear(); } } my_map.insert(pair<int,int>(nums[i],i)); } return result; } };
双指针
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; sort(nums.begin(),nums.end()); int left ,right; for(int i=0 ; i<nums.size()-1;i++) { if(nums[i] > 0) break; if(i>0 && nums[i] == nums[i-1]) continue; left = i+1; right = nums.size()-1; while(left<right) { if(nums[i] + nums[left] + nums[right] > 0) right--; else if(nums[i] + nums[left] + nums[right] < 0) left++; else if(nums[i] + nums[left] + nums[right] == 0) { vector<int> tmp={nums[i] , nums[left] , nums[right]}; result.push_back(tmp); while(left<right && nums[right]==nums[right-1]) right--; while(left<right && nums[left]==nums[left+ 1]) left++; right--; left++; } } } return result; } };
高频题
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; sort(nums.begin(),nums.end()); int j,k; for(int i=0 ; i<nums.size() ;i++) { if(nums[i] > 0) break; if(i>0 && nums[i] == nums[i-1]) continue; j = i+1; k = nums.size()-1; while(j<k) { if (nums[i] + nums[j] + nums[k] >0) k--; else if(nums[i] + nums[j] + nums[k] <0) j++; else if(nums[i] + nums[j] + nums[k] == 0) { result.push_back({nums[i],nums[j],nums[k]}); while(j<k && nums[k] == nums[k-1]) k--; while(j<k && nums[j] == nums[j+1]) j++; k--; j++; } } } return result; } };
