【题目】
Given an array nums of n integers, are there elements a, b, c in nums 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.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
【思路】
拓展四数之和：https://www.cnblogs.com/inku/p/9977917.html
sort后，头尾两个指针。
sum=0,left++,right--,继续遍历，向中间逼近。
sum>0,right--，需要更小的数使之满足。
sum<0,left++，需要更大的数使之满足。
if(sum==0){
data.add(Arrays.asList(nums[i],nums[left], nums[right]));
left++;
right--;
while(left<right&&nums[left]==nums[left-1])
left++;
while(left<right&&nums[right]==nums[right+1])
right--;
}
else if(left<right&&sum>0)
right--;
else
left++;
}答案去重
if(i>0&&nums[i]==nums[i-1]) continue;
while(left<right&&nums[left]==nums[left-1]) left++;
while(left<right&&nums[right]==nums[right+1]) right--;
【代码】
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> data=new ArrayList<>();
Arrays.sort(nums);
for(int i=0;i<nums.length-2;i++){
int left=i+1;
int right=nums.length-1;
if(i>0&&nums[i]==nums[i-1]){
continue;}
while(left<right){
int sum=nums[left]+nums[right]+nums[i];
if(sum==0){
data.add(Arrays.asList(nums[i],nums[left], nums[right]));
left++;
right--;
while(left<right&&nums[left]==nums[left-1])
left++;
while(left<right&&nums[right]==nums[right+1])
right--;
}
else if(left<right&&sum>0)
right--;
else
left++;
}
}
return data;
}
}