给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
方法一：
写了一个效率极低的实现，备份以示警戒！! ！ 力扣耗时 140 ms
把数据分组，负数、正数，并且标记好是否重复; 再分情况计算各种情况;
class Solution { struct Element { int value; int times; Element(int value, int times):value(value),times(times){}; }; public: vector<vector<int>> threeSum(vector<int>& nums) { if(nums.size()<3) return {}; vector<vector<int>> rs; Element zero(0, 0); // zero vector<Element*> plusVec; // plus vector<Element*> minusVec; // minus map<int, Element*> plusMap; // plus value to Element map map<int, Element*> minusMap; // minus value to Element map this->initElement(nums, zero, plusVec, minusVec, plusMap, minusMap); if(zero.times > 2) rs.push_back({0,0,0}); // {0, 0, 0} if(zero.times > 0) // {0, minus, plus} { for(auto it=plusMap.begin(); it!=plusMap.end(); it++) { Element *element = it->second; if(minusMap.find(-element->value) == minusMap.end()) continue; rs.push_back({minusMap[-element->value]->value, 0, element->value}); } } appendElement(rs, minusVec, plusMap); // {minus, minus, plus} appendElement(rs, plusVec, minusMap); // {minus, plus, plus} return rs; } void initElement(vector<int>& nums, Element &zero, vector<Element*> &plusVec, vector<Element*> &minusVec, map<int, Element*> &plusMap, map<int, Element*> &minusMap) { for(int i=0; i<nums.size(); i++) { if(nums[i] == 0) { zero.times++; continue; } if(nums[i] > 0) { if(plusMap.find(nums[i]) == plusMap.end()) { Element *element = new Element(nums[i], 1); plusMap[element->value] = element; plusVec.push_back(element); } else (plusMap[nums[i]]->times)++; continue; } if(nums[i] < 0) { if(minusMap.find(nums[i]) == minusMap.end()) { Element *element = new Element(nums[i], 1); minusMap[element->value] = element; minusVec.push_back(element); } else (minusMap[nums[i]]->times)++; } } } void appendElement(vector<vector<int>> &rs, vector<Element*> &elementVec, map<int, Element*> &cmap) { for(int i=0; i<elementVec.size(); i++) // {minus, minus, plus} { Element *element = elementVec[i]; if(element->times>1 && cmap.find(-element->value*2) != cmap.end()) { rs.push_back({element->value, element->value, cmap[-element->value*2]->value}); } for(int j=i+1; j<elementVec.size(); j++) { Element *element2 = elementVec[j]; if(cmap.find(-element->value-element2->value) != cmap.end()) { rs.push_back({element->value, element2->value, cmap[-element->value-element2->value]->value}); } } } } };
方法二：
效率略微提升一点的做法： 力扣耗时 160 ms
还是效率不行，更费时！！
把数据存入map结构，用于去重，并记录是否重复;
先定位左边界，再从右边界向前遍历所有情况;
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { if(nums.size()<3) return {}; this->init(nums); vector<vector<int>> rs; // result if(zero > 2) rs.push_back({0,0,0}); // {0, 0, 0} for(auto it=plusMap.begin(); it!=plusMap.end(); it++) { if(it->first >= 0) break; if(it->second && plusMap.find(-2*it->first)!=plusMap.end()) // {-2, -2, 4} { rs.push_back({it->first, it->first, -2*it->first}); } auto it2 = plusMap.lower_bound(-2*it->first); // the right bound for( ;it2!=plusMap.begin(); ) { it2--; int mid = -it->first - it2->first; if(mid >= it2->first) break; if(plusMap.find(mid) == plusMap.end()) continue; // not find rs.push_back({it->first, mid, it2->first}); } if(it->first%2==0) //{-4, 2, 2} { auto right = plusMap.find(-it->first/2); if(right!=plusMap.end() && right->second) rs.push_back({it->first, right->first, right->first}); } } return rs; } void init(vector<int>& nums) { for(int i=0; i<nums.size(); i++) { if(nums[i] == 0) zero++; plusMap[nums[i]] = (plusMap.find(nums[i]) != plusMap.end()); } } private: int zero = 0; // zero map<int, bool> plusMap; // plus value to Element map };
方法三：
用数组存放去重、排序后的数据。 力扣耗时 216 ms
更费时了，效率还是很低，依然存在大量的重复比较; 双指针用的地方不对？？？ 可是三个变量，如何用双指？？？
用二分查找，判定中间元素是否存在。
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { if(nums.size()<3) return {}; this->init(nums); vector<vector<int>> rs; // result if(_zero > 2) rs.push_back({0,0,0}); // {0, 0, 0} int len = _values.size(); for(int i=0; i<len; i++) { if(_values[i] >= 0) break; for(int j=len-1; j>0; j--) { int mid = -_values[i] - _values[j]; if(mid > _values[j]) break; int index = this->find(i, j, mid); if(index == - 1) continue; // not find if(index == i && !_marks[i]) continue; if(index == j && !_marks[j]) continue; rs.push_back({_values[i], mid, _values[j]}); } } return rs; } /** 二分查找 */ int find(int left, int right, int target) { while(left<=right) { int mid = (left + right) / 2; if(target == _values[mid]) return mid; else if(target > _values[mid]) left = mid + 1; else if(target < _values[mid]) right = mid - 1; } return -1; } /** 初始化 */ void init(vector<int>& nums) { map<int, bool> plusMap; // plus value to Element map for(int i=0; i<nums.size(); i++) { if(nums[i] == 0) _zero++; plusMap[nums[i]] = (plusMap.find(nums[i]) != plusMap.end()); } for(auto it = plusMap.begin(); it!=plusMap.end(); it++) { _values.push_back(it->first); _marks.push_back(it->second); } } private: int _zero = 0; // zero vector<int> _values; // values with no repeat vector<bool> _marks; // repeat or not };
方法四：
用数组存放去重、排序后的数据。 力扣耗时 36 ms
不再用二分查找判定中间元素;
先固定最左边的数字，再定义双指针 left right分别表示中间和右边的索引;
由于数据已去重、排序，这样left 、right就可以省去大量无意义比较;
果然，耗时有质的飞跃！！
但是所占内存还是太大。
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { if(nums.size()<3) return {}; this->init(nums); vector<vector<int>> rs; // result if(_zero > 2) rs.push_back({0,0,0}); // {0, 0, 0} for(int i=0; i<_values.size(); i++) { if(_values[i] >= 0) break; int target = -_values[i]; int left = i; int right = _values.size() - 1; while(left<=right) { int add = _values[left] + _values[right]; if(add == target) // find { if(left == i && !_marks[left]) {left++; right--; continue; } if(left == right && !_marks[left]) {left++; right--; continue; } rs.push_back({_values[i], _values[left], _values[right]}); left++; right--; } else if(add > target) right--; else if(add < target) left++; } } return rs; } /** 初始化 */ void init(vector<int>& nums) { map<int, bool> plusMap; // plus value to Element map for(int i=0; i<nums.size(); i++) { if(nums[i] == 0) _zero++; plusMap[nums[i]] = (plusMap.find(nums[i]) != plusMap.end()); } for(auto it = plusMap.begin(); it!=plusMap.end(); it++) { _values.push_back(it->first); _marks.push_back(it->second); } } private: int _zero = 0; // zero vector<int> _values; // values with no repeat vector<bool> _marks; // repeat or not };
方法五：
首先去重、排序，记录重复，数组存储;
重点！！ 改用指针遍历数据体，指针可以作自增、自减、加、减、判大小，更能方便定位数值;
再次运行， 力扣耗时 24ms ，超过 100%的用户！！
可是内存消耗还是大。
### 解题思路
1、数据去重、升序排列、记录重复，中间过程用到map的有序特性，之后用两数组存储数据;
2、固定最左侧数据，定义双指针分别表示中间和右侧;
3、循环双指针while(left<=right){}，使其向彼此靠拢;
4、由于数据为升序排列，可省去大量无用判断;
5、注意边界条件，左侧与中间重合、右侧与中间重合的情况;
6、用指针速度更快;
6、本解法内存消耗大，有待优化；
### 代码如下：
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { if(nums.size()<3) return {}; this->init(nums); vector<vector<int>> rs; // result if(_zero > 2) rs.push_back({0,0,0}); // {0, 0, 0} int *start = &_values[0]; int *end = _values.size() - 1 + start; for(int *p=start; p<=end; p++) { if(*p >= 0) break; int *left = p; int *right = end; while(left<=right) { int add = *left + *right; if(add == -*p) // find { if(left == p && !_marks[left-start]) {left++; right--; continue; } if(left == right && !_marks[left-start]) {left++; right--; continue; } rs.push_back({*p, *left, *right}); left++; right--; } else if(add > -*p) right--; else if(add < -*p) left++; } } return rs; } /** 初始化 */ void init(vector<int>& nums) { map<int, bool> plusMap; // plus value to map for(int i=0; i<nums.size(); i++) { if(nums[i] == 0) _zero++; plusMap[nums[i]] = (plusMap.find(nums[i]) != plusMap.end()); } for(auto it = plusMap.begin(); it!=plusMap.end(); it++) { _values.push_back(it->first); _marks.push_back(it->second); } } private: int _zero = 0; // zero vector<int> _values; // values with no repeat vector<bool> _marks; // repeat or not };