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