FilesExpand file tree

 master

/

3Sum.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

39 lines (38 loc) · 1.03 KB

 master

/

3Sum.java

Copy path

Top

File metadata and controls

• Code
• Blame

39 lines (38 loc) · 1.03 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

34

35

36

37

38

39

/*

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)

*/

public class Solution {

public List<List<Integer>> threeSum(int[] num) {

List<List<Integer>> rst = new ArrayList<List<Integer>>();

Arrays.sort(num);

for (int i = 0; i < num.length-2; i++) {

int m = i + 1, n = num.length-1;

while (m < n) {

int sum = num[i] + num[m] + num[n];

if (sum == 0) {

List<Integer> list = new ArrayList<Integer>();

list.add(num[i]);

list.add(num[m]);

list.add(num[n]);

rst.add(list);

m++;

} else if (sum > 0) {

n--;

} else {

m++;

}

}

}

Set<List<Integer>> set = new HashSet<Integer>(rst);

rst.clear();

rst.addAll(set);

return rst;

}

}