GeezerVison is showing github.com — Algorithm/java/coding/3Sum.java at master · lelea2/Algorithm

Expand file tree

3Sum.java

Copy path

More file actions

Latest commit

History

51 lines (48 loc) · 1.9 KB

3Sum.java

Copy path

File metadata and controls

51 lines (48 loc) · 1.9 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

//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.

//Complexity: O(n^2)

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

ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

if (num.length < 3) { //If given array is less than 3 number, just returned right away

return result;

}

// sort array (assume that array being sorted)

// If array is sorted, we can start keep track of 2 pointer

// and move pointer from the beginning or the end up or down by compare to the negate value

Arrays.sort(num);

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

// //avoid duplicate solutions

if (i == 0 || num[i] > num[i - 1]) {

int negate = -num[i];

int start = i + 1; //start pointer, first of the array

int end = num.length - 1; //end pointer, end of the array

while (start < end) {

//case 1

if (num[start] + num[end] == negate) {

ArrayList<Integer> temp = new ArrayList<Integer>();

temp.add(num[i]);

temp.add(num[start]);

temp.add(num[end]);

result.add(temp);

start++;

end--;

//avoid duplicate solutions

while (start < end && num[end] == num[end + 1]) {

end--;

}

while (start < end && num[start] == num[start - 1]) {

start++;

}

//case 2

} else if (num[start] + num[end] < negate) {

start++;

//case 3

} else {

end--;

}

return result;

}