3Sum问题

3Sum

## [更多技术博客 http://vilins.top/](http://vilins.top/)

1.题目

Given an arraynumsofnintegers, are there elementsa,b,cinnumssuch thata+b+c= 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]

2. 分析

与这题类似的题目如下LeetCode--3Sum Closest-CSDN博客

这里需要找三个数相加的和等于0，那么我们将问题进行一下转化，先将三个数的相加转化为两个数的相加，也就是说，我们先确定一个数，它是作为遍历的标记，然后这个数的下一个数作为begin，数组最后一个数作为end，从两边进行逼近，也就是说，但这两个数的和比target小的时候，begin++；当这两个数的和比target大的时候，end--；不过这种操作的前提是数组是有序的。为了避免相同元组，我们先用set存，最后转化为vector；为避免nums元素相同而浪费时间，我们用flag做标记。

3. 源码

class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { set<vector<int> > result; int flag = 0; if(nums.size() == 0) { return vector<vector<int> >(); } for(int i = 0; i < nums.size() - 1; i++) { for(int j = 0; j < nums.size() - i - 1; j++) { if(nums[j] > nums[j+1]) { int temp = nums[j]; nums[j] = nums[j+1]; nums[j+1] = temp; } } } if(nums[0] == nums[nums.size() - 1]) { flag = 1; } int begin = 0, end = nums.size() - 1; for(int i = 0; i < nums.size(); i++) { //cout << "ll" << endl; begin = i + 1; end = nums.size() - 1; int target = 0 - nums[i]; while(begin < end) { if(nums[begin] + nums[end] < target) { begin++; } else if(nums[begin] + nums[end] > target) { end--; } else { vector<int> r; r.push_back(nums[i]); r.push_back(nums[begin]); r.push_back(nums[end]); result.insert(r); begin++; if(flag == 1) { break; } } } } vector<vector<int> > v_result(result.begin(), result.end()); return v_result; } };

## [更多技术博客 http://vilins.top/](http://vilins.top/)