Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
2sum的升级版。依然用了map。用的时候注意当前使用元素应该删除。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 |
class
Solution {public: vector<vector<int> > threeSum(vector<int> &num) { map<int
, int>m; vector< vector<int> >re; for(int
i = 0 ; i < num.size();i++) m[num[i]]++; for(map<int,int>::iterator it = m.begin() ; it != m.end();it++) { int
now = it->first; int
target = 0 - now; m[now]--; for(map<int,int>::iterator iter = it ; iter!= m.end() ; iter++) { if(iter->second <= 0)continue; m[iter->first]--; int
tar = target - iter->first; if(m.find(tar) != m.end()&&tar>=iter->first&&m[tar]>0) { vector<int> tmp; tmp.push_back(it->first); tmp.push_back(iter->first); tmp.push_back(tar); re.push_back(tmp); } m[iter->first]++; } m[now]++; } return
re; }}; |
原文：http://www.cnblogs.com/pengyu2003/p/3585376.html