Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Example 2:
Input: nums = []
Output: []
Example 3:
Input: nums = [0]
Output: []
思路：排序+双指针。三个数(a,b,c)和为0，先对数组从小到大排序，固定最左边的a, 然后在右边的序列中寻找和为-a的b和c。
nums
怎么找b和c呢？因为数组是有序的，如上图那样，固定了nums[i],让i在最外层循环，left取i+1，right取数组最后一个，要寻找满足nums[left]+nums[right] +nums[i] =0的left和right，在while(left<right)中判断三数之和sum与0的大小关系。等于0装入结果集，小于0 left右移，大于0 right左移。
注意：
1.先解决一下数组长度小于3 和等于3的情况。
2.结果不重复，所以先用Set<List<Integer>>保存结果；
3.最外层i的循环需要判断nums[i] 是否等于nums[i-1], 相等可以直接跳过；
1.如果排序之后最左边的值nums[i] >0,所以不可能后面都是比0大，可以直接跳出循环。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Set<List<Integer>> set = new HashSet<>();
if(nums.length < 3){
return result;
}
if(nums.length == 3){
if(nums[0] + nums[1] + nums[2] == 0){
List<Integer> list = new ArrayList<>();
list.add(nums[0]);
list.add(nums[1]);
list.add(nums[2]);
result.add(list);
}
return result;
}
Arrays.sort(nums);
for(int i=0; i<nums.length-2; i++){
if(i>0 && nums[i]==nums[i-1]){//从i=1开始判断是否与前一个重复
continue;
}
if(nums[i] > 0){
break;//后面都是大于0的，没有解了
}
int left = i+1;
int right = nums.length - 1;
while(left < right){
int sum = nums[i] + nums[left] + nums[right];
if(sum == 0){
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[left]);
list.add(nums[right]);
set.add(list);
}
if(sum < 0){
left++;
}else{
right--;
}
}
}
for(List<Integer> l : set){
result.add(l);
}
return result;
}
}
