Three Sum
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. 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.
Example:
For example, given array S = {-1 0 1 2 -1 -4}, A solution set is:
(-1, 0, 1)
(-1, -1, 2)
Solution:
Extension of Two Sum. Run two sum inside a for loop.
Code:
public class Solution {
/**
* @param numbers : Give an array numbers of n integer
* @return : Find all unique triplets in the array which gives the sum of zero.
*/
public ArrayList<ArrayList<Integer>> threeSum(int[] numbers) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if (numbers == null || numbers.length == 0) {
return res;
}
Arrays.sort(numbers);
HashSet<ArrayList<Integer>> hset = new HashSet<>();
for (int i = 0; i < numbers.length; i++) {
int left = i + 1;
int right = numbers.length - 1;
while (left < right) {
int num = numbers[i] + numbers[left] + numbers[right];
if (num == 0) {
ArrayList<Integer> temp = new ArrayList<>();
temp.add(numbers[i]);
temp.add(numbers[left]);
temp.add(numbers[right]);
Collections.sort(temp);
hset.add(temp);
left++;
right--;
} else if (num > 0) {
right--;
} else {
left++;
}
}
}
for (ArrayList<Integer> temp : hset) {
res.add(temp);
}
return res;
}
}