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.
Notice
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.
Analysis
考虑non-descending，先sort数组，其次考虑去除duplicate；
类似2sum，可以利用two pointers，不断移动left 和 right 指针，直到找到目标，或者两指针相遇
大概思路是外围for-loop一遍数组，然后在每次迭代的时候，设置[l, r]的区间，区间范围为l , r = i + 1, len(nums) - 1, 这样比对的数就有3个，分别是nums[i], nums[l] 和 nums[r].
最终要达到的效果是:
nums[l] + nums[r] == -nums[i]
这道题一定要记住去重，不仅仅是区间的l和r要去重，外围的i也需要去重。去重的方法如下:
i去重：if i == 0 or nums[i] > nums[i-1]:
l去重：while l < r and nums[l] == nums[l-1]: l += 1
r去重：while l < r and nums[r] == nums[r+1]: r -= 1
Solution
Two Pointers - (40ms, 97.77%)
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length < 3) {
return res;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int j = i + 1;
int k = nums.length - 1;
int target = 0 - nums[i];
while (j < k) {
if (nums[j] + nums[k] > target) {
k--;
} else if (nums[j] + nums[k] < target) {
j++;
} else {
res.add(Arrays.asList(nums[i], nums[j], nums[k]));
j++;
k--;
// skip duplicates
while (j < k && nums[j] == nums[j - 1]) {
j++;
}
while (j < k && nums[k] == nums[k + 1]) {
k--;
}
}
}
}
return res;
}
}
Another Two Pointer
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>> result = new ArrayList<ArrayList<Integer>>();
if (numbers == null || numbers.length < 3) {
return result;
}
Arrays.sort(numbers);
for (int i = 0; i < numbers.length - 2; i++) {
if (i > 0 && numbers[i] == numbers[i - 1]) {
continue;
}
int left = i + 1;
int right = numbers.length - 1;
while (left < right) {
int sum = numbers[i] + numbers[left] + numbers[right];
if (sum == 0) {
ArrayList<Integer> tmp = new ArrayList<Integer>();
tmp.add(numbers[i]);
tmp.add(numbers[left]);
tmp.add(numbers[right]);
result.add(tmp);
left++;
right--;
while (left < right && numbers[left] == numbers[left - 1]) {
left++;
}
while (left < right && numbers[right] == numbers[right + 1]) {
right--;
}
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
}