C++
把3个数求和，转变为2个数求和
1. 把数组排序
2. 注意过滤重复值
3. 从前到后遍历，游标i
4. 从后边数中找start ＋ end ＝ -arr[i]的2 sum
5. start ＋ end < -arr[i], start++
6. start + end > -arr[i], end--
7. start + end = -arr[i], insert <i, start, end> into result vecotr
1 class Solution { 2 public: 3 /** 4 * @param numbers : Give an array numbers of n integer 5 * @return : Find all unique triplets in the array which gives the sum of zero. 6 */ 7 vector<vector<int> > threeSum(vector<int> &nums) { 8 // write your code here 9 vector<vector<int> > result; 10 11 sort(nums.begin(), nums.end()); 12 for (int i = 0; i < nums.size(); i++) { 13 if (i > 0 && nums[i] == nums[i - 1]) { 14 continue; 15 } 16 // two sum; 17 int start = i + 1, end = nums.size() - 1; 18 int target = -nums[i]; 19 while (start < end) { 20 if (start > i + 1 && nums[start - 1] == nums[start]) { 21 start++; 22 continue; 23 } 24 if (nums[start] + nums[end] < target) { 25 start++; 26 } else if (nums[start] + nums[end] > target) { 27 end--; 28 } else { 29 vector<int> triple; 30 triple.push_back(nums[i]); 31 triple.push_back(nums[start]); 32 triple.push_back(nums[end]); 33 result.push_back(triple); 34 start++; 35 } 36 } 37 } 38 39 return result; 40 } 41 };
本文转自ZH奶酪博客园博客，原文链接：http://www.cnblogs.com/CheeseZH/p/5009646.html，如需转载请自行联系原作者
