生活随笔
收集整理的这篇文章主要介绍了
【leetcode】3Sum
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
3Sum 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:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solution set must not contain duplicate triplets. For example, given array S = {-1 0 1 2 -1 -4},A solution set is:(-1, 0, 1)(-1, -1, 2) 先对数组进行排序，从头开始扫描，扫描的数作为固定的数。 a=num[i]; 当固定了一个数以后， 选取b=num[i+1]=num[j] 选取c=num[n-1]=num[k] 若a+b+c=0 则找到了一个a，b，c，记录下来，j++,k--继续扫描 若a+b+c<0 则j++ 若a+b+c>0 则k-- 要注意去重的问题： 1.若num[i]=num[i-1]，则跳过 2.若num[j]=num[j-1]，则跳过 3.若num[k]=num[k+1]，则跳过
1 class Solution {
2 public :
3 vector<vector<
int > > threeSum(vector<
int > &
num) {
4
5 int n=
num.size();
6 sort(num.begin(),num.end());
7
8 int i,j,k;
9 int a,b,c;
10 vector<vector<
int > >
result;
11
12 for (i=
0 ;i<n-
2 ;i++
)
13 {
14 j=i+
1 ;
15 k=n-
1 ;
16
17 while (j<
k)
18 {
19 a=
num[i];
20 if (i>
0 &&num[i]==num[i-
1 ])
21 {
22 break ;
23 }
24 b=
num[j];
25 if (j>i+
1 &&num[j]==num[j-
1 ])
26 {
27 j++
;
28 continue ;
29 }
30
31 c=
num[k];
32 if (k<n-
1 &&num[k]==num[k+
1 ])
33 {
34 k--
;
35 continue ;
36 }
37
38 if (a+b+c==
0 )
39 {
40 vector<
int > tmp(
3 );
41 tmp[
0 ]=
a;
42 tmp[
1 ]=
b;
43 tmp[
2 ]=
c;
44 result.push_back(tmp);
45 j++
;
46 k--
;
47 }
48 else if (a+b+c<
0 )
49 {
50 j++
;
51 }
52 else if (a+b+c>
0 )
53 {
54 k--
;
55 }
56 }
57 }
58
59 return result;
60
61 }
62 };
63
转载于:https://www.cnblogs.com/reachteam/p/4190319.html
总结
以上是生活随笔 为你收集整理的【leetcode】3Sum 的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔 网站内容还不错，欢迎将生活随笔 推荐给好友。
