FilesExpand file tree

 master

/

3sum.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

executable file

·

70 lines (64 loc) · 2.24 KB

 master

/

3sum.java

Copy path

Top

File metadata and controls

• Code
• Blame

executable file

·

70 lines (64 loc) · 2.24 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

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

import java.util.Arrays;

class Solution {

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

List<List<Integer>> result = new LinkedList<>();

// Defensive technique to check zero

if (nums.length > 2) {

List<Integer> zeros = new LinkedList<>();

for (int i = 0; i < 3; i++) {

if (nums[i] != 0) break;

zeros.add(0);

if (i == nums.length-1) {

result.add(zeros);

return result;

}

}

}

// HashSet<Integer> set = new HashSet<Integer>();

Arrays.sort(nums);

// Show nums array

for (int i = 0; i < nums.length; i++)

System.out.print(nums[i] + " ");

System.out.println();

// Do binary search for each pairs i and j

int lasti = Integer.MAX_VALUE;

int lastj = Integer.MAX_VALUE;

for (int i = 0; i < nums.length; i++) {

if (nums[i] == lasti)

continue;

for (int j = i+1; j < nums.length; j++) {

if (nums[j] == lastj)

continue;

int complements = -(nums[i] + nums[j]);

int lo = 0;

int hi = nums.length - 1;

int k = -1;

while (lo <= hi) {

int mid = lo + (hi - lo) / 2;

if (complements < nums[mid]) hi = mid - 1;

else if (complements > nums[mid]) lo = mid + 1;

else {

k = mid;

break;

}

}

if (k == i && k+1 < nums.length)

if (nums[k+1] == nums[i])

k++;

if (k == j && k+1 < nums.length)

if (nums[k+1] == nums[j])

k++;

if (k > j) {

List<Integer> newSum = new LinkedList<>();

newSum.add(nums[i]);

newSum.add(nums[j]);

newSum.add(nums[k]);

result.add(newSum);

}

lastj = nums[j];

}

lasti = nums[i];

}

return result;

}

}