1 排序
2 双指针 位置卡死逐步对着移动 左右2个指针
3 while 跳过重复的数
双指针
class Solution {
public:vector<vector<int>> my_test1(vector<int>& nums) {std::set<int> index_set;std::map<std::set<int>,vector<int>> result_map;vector<vector<int>> result_vector;//sort(nums.begin(),nums.end());//std::cout<< nums << std::endl;for(int i=0;i<nums.size()-2;i++){for(int j=i+1;j<nums.size()-1;j++){ for(int z=j+1;z<nums.size();z++){int all_=nums[i]+nums[j]+nums[z];if(all_==0){// index_set.insert(nums[i]);// index_set.insert(nums[j]);// index_set.insert(nums[z]);result_map.insert({{nums[i],nums[j],nums[z]},{nums[i],nums[j],nums[z]}});break;} }}}for (auto &it : result_map){result_vector.push_back(it.second);}return result_vector;}vector<vector<int>> my_test2(vector<int>& nums) {std::set<int> index_set;std::map<std::set<int>,vector<int>> result_map;vector<vector<int>> result_vector;unordered_multiset<int> sourc_udset(nums.begin(), nums.end());//sort(nums.begin(),nums.end());std::cout<< nums.size() << std::endl;for(int i=0;i<nums.size()-2;i++){for(int j=i+1;j<nums.size()-1;j++){ int target=0-nums[i]-nums[j];auto range = sourc_udset.equal_range(target);size_t count = std::distance(range.first, range.second);if(target==nums[i] && target==nums[j] ){ if (count >= 3) {result_map.insert({{nums[i],nums[j],target},{nums[i],nums[j],target}});//auto second = std::next(range.first);// 安全访问第二个} else {std::cout << "没有第二个匹配元素" << std::endl;}}else if(target==nums[i] || target==nums[j] ){if (count >= 2) {result_map.insert({{nums[i],nums[j],target},{nums[i],nums[j],target}});}}else{if (count >=1) {result_map.insert({{nums[i],nums[j],target},{nums[i],nums[j],target}});}}}}for (auto &it : result_map){result_vector.push_back(it.second);}return result_vector;}vector<vector<int>> my_test3(vector<int>& nums) {std::set<int> index_set;std::map<std::set<int>,vector<int>> result_map;vector<vector<int>> result_vector;unordered_multiset<int> sourc_udset(nums.begin(), nums.end());sort(nums.begin(),nums.end());// 先排序std::cout<< nums.size() << std::endl;bool stop=0;int lastZ=nums.size()-1;for(int i=0;i<nums.size()-2;i++){if(nums[i]>0) return result_vector; // 排序前提下 第一个数大于0，直接挂for(int j=i+1;j<nums.size()-1;j++){ if((nums[i]+nums[j])>0) {return result_vector;}// 排序前提下 第一个数+第二个数 大于0，直接挂for(int z=lastZ;z>j;z--){ int temp_=nums[i]+nums[j]+nums[z];if(temp_==0){result_map.insert({{nums[i],nums[j],nums[z]},{nums[i],nums[j],nums[z]}});stop=1;lastZ=z;break; }else if(temp_<0){// 排序前提下 这个j小不行j++ z已经最大lastZ=z;break; }else{// 大于0 排序前提下 必然在 j-z之间 z是最大的往下降 z--lastZ=z;}}if(stop){ stop=0;break;}}}for (auto &it : result_map){result_vector.push_back(it.second);}return result_vector;}vector<vector<int>> my_test4(vector<int>& nums) {// std::set<int> index_set;std::map<std::set<int>,vector<int>> result_map;vector<vector<int>> result_vector;// unordered_multiset<int> sourc_udset(nums.begin(), nums.end());sort(nums.begin(),nums.end());// 先排序std::cout<< nums.size() << std::endl;for(int i=0;i<nums.size()-2;i++){if(nums[i]>0) {break; // 排序前提下 第一个数大于0，直接挂}int qian=i+1;int hou=nums.size()-1;while(qian<hou){int temp2= nums[qian]+nums[i];if(temp2>0){break;}while(qian<hou){//cout<< i << " / " << nums[i] << " " << qian << " / " << nums[qian] << " " << hou<< " / " << nums[hou] <<endl;int temp3= nums[qian]+nums[i]+nums[hou];if(temp3>0){hou--;while(nums[hou]==nums[hou+1] && hou>qian){hou--;}}else if(temp3==0){// cout<< " 成功 "<< i << " / " << nums[i] << " " << qian << " / " << nums[qian] << " " << hou<< " / " << nums[hou] <<endl;//result_map.insert({{nums[i],nums[qian],nums[hou]},{nums[i],nums[qian],nums[hou]}});result_vector.push_back({nums[i],nums[qian],nums[hou]});qian++;while(nums[qian]==nums[qian-1] && qian<hou){qian++;}while(nums[i]==nums[i+1] && i<nums.size()-2 ){i++;}break;}else{qian++;while(nums[qian]==nums[qian-1]&& qian<hou){qian++;}}//if(nums[hou]==nums[hou-1] && qian<(hou-1))hou--; }}}for (auto &it : result_map){//cout<< " 加入"<<endl;result_vector.push_back(it.second);}return result_vector;}vector<vector<int>> threeSum(vector<int>& nums) {// return my_test1(nums);return my_test4(nums);}
};
参考答案
官方
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int n = nums.size();sort(nums.begin(), nums.end());vector<vector<int>> ans;// 枚举 afor (int first = 0; first < n; ++first) {// 需要和上一次枚举的数不相同if (first > 0 && nums[first] == nums[first - 1]) {continue;}// c 对应的指针初始指向数组的最右端int third = n - 1;int target = -nums[first];// 枚举 bfor (int second = first + 1; second < n; ++second) {// 需要和上一次枚举的数不相同if (second > first + 1 && nums[second] == nums[second - 1]) {continue;}// 需要保证 b 的指针在 c 的指针的左侧while (second < third && nums[second] + nums[third] > target) {--third;}// 如果指针重合，随着 b 后续的增加// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环if (second == third) {break;}if (nums[second] + nums[third] == target) {ans.push_back({nums[first], nums[second], nums[third]});}}}return ans;}
};作者：力扣官方题解
链接：https://leetcode.cn/problems/3sum/solutions/284681/san-shu-zhi-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
网友
class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums); // 先排序List<List<Integer>> res = new ArrayList<>();for (int i = 0; i < nums.length; i++) {// 跳过重复元素if (i > 0 && nums[i] == nums[i - 1]) continue;// 双指针，目标是找到 nums[l] + nums[r] = -nums[i]int l = i + 1, r = nums.length - 1;int target = -nums[i];while (l < r) {int sum = nums[l] + nums[r];if (sum == target) {res.add(Arrays.asList(nums[i], nums[l], nums[r]));l++;r--;// 跳过重复元素while (l < r && nums[l] == nums[l - 1]) l++;while (l < r && nums[r] == nums[r + 1]) r--;} else if (sum < target) {l++;} else {r--;}}}return res;}
}