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: 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]
]
一刷
有两种思路。
先排序再用双指针
Time complexity O(n^2), space complexity O(1)使用Two Sum的方法， 遍历 + HashMap
Time complexity O(n^2), space complexity O(n)
HashMap 在我们需要返回indices比较有用，因为sort之后indices无法一一对应
方法1:
public 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);
//eliminate the duplicate ones
for(int i=0; i<nums.length-2; i++){
if (i > 0 && nums[i] == nums[i - 1]) continue;
int lo = i+1;
int hi = nums.length - 1;
while(lo < hi){
if(nums[i] + nums[lo] + nums[hi] == 0){
Integer[] array = {nums[i], nums[lo], nums[hi]};
res.add(Arrays.asList(array));
hi--;
while(hi>=0 && nums[hi] == nums[hi+1]) hi--;
lo++;
while(lo<nums.length && nums[lo] == nums[lo-1]) {
lo++;
}
}
else if(nums[i] + nums[lo] + nums[hi] > 0){
hi--;
}
else {
lo++;
}
}
}
return res;
}
}
