3 Sum leetcode java

4703 ワード

LeetCode

タイトル:
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)

  ：
 3 Sum two Sum   ，    two sum           。
    two sum      ：  duplicate  ，3          index。
   ，       。
   ， 0            （num.length-3)，    ，  num[i]  3sum       ，   i+1     ，  2sum   。
      3sum==0    ，       hashset    ，     。(  hashset value   ）
        ，      ，    ，low high      。
 
       O(n2)
      ：

1
public ArrayList> threeSum(
int[] num) {
2         ArrayList> res =
new ArrayList>();
3
if(num.length<3||num ==
null)
4
return res;
5
6         HashSet> hs =
new HashSet>();
7
8         Arrays.sort(num);
9
10
for(
int i = 0; i <= num.length-3; i++){
11
int low = i+1;
12
int high = num.length-1;
13
while(low//
since they cannot be the same one, low should not equal to high
14

int sum = num[i]+num[low]+num[high];
15
if(sum == 0){
16                     ArrayList unit =
new ArrayList();
17                     unit.add(num[i]);
18                     unit.add(num[low]);
19                     unit.add(num[high]);
20
21
if(!hs.contains(unit)){
22                         hs.add(unit);
23                         res.add(unit);
24                     }
25
26                     low++;
27                     high--;
28                 }
else
if(sum > 0)
29                     high --;
30
else
31                     low ++;
32             }
33         }
34
35
return res;
36     }



   ，  duplicate  ，              ，          ， 3                 ，        ，    ：

1
public ArrayList> threeSum(
int[] num) {
2         ArrayList> res =
new ArrayList>();
3
if(num.length<3||num ==
null)
4
return res;
5
6         Arrays.sort(num);
7
8
for(
int i = 0; i <= num.length-3; i++){
9
if(i==0||num[i]!=num[i-1]){
//
remove dupicate
10

int low = i+1;
11
int high = num.length-1;
12
while(low13
int sum = num[i]+num[low]+num[high];
14
if(sum == 0){
15                         ArrayList unit =
new ArrayList();
16                         unit.add(num[i]);
17                         unit.add(num[low]);
18                         unit.add(num[high]);
19
20                         res.add(unit);
21
22                         low++;
23                         high--;
24
25
while(low//
remove dupicate
26
                            low++;
27
while(low//
remove dupicate
28
                            high--;
29
30                     }
else
if(sum > 0)
31                         high --;
32
else
33                         low ++;
34                 }
35             }
36         }
37
return res;
38     }

JavaでKugouからダウンロードした音楽をアレンジ

2010.07.03———IEの下のoptionでclickが使えない問題について