image.png
（※这道题有点复杂——中等题）
思路：
1）先对数组进行排序，排序后固定一个数nums[i]，在使用左右指针指向nums[i]后面两端，分别是nums[L]和nums[R]，计算三个数的和是否满足nums[left]+nums[right]==target，如果满足，添加到结果集
2）如果nums[i]大于0，则三数之和必然大于0，结束循环
3）如果nums[i] == nums[i-1],则说明该数字重复，会导致结果重复，所以应该跳过。
4）nums[left]+nums[right]==target时，nums[L] == nums[L+1],会导致结果重复，所以应该跳过,L++
5）nums[left]+nums[right]==target时，nums[R] == nums[R−1] 则会导致结果重复，应该跳过，R−−
public static List<List<Integer>> threeSum(int[] nums){
//总时间复杂度:O(n^2)
List<List<Integer>> ans = new ArrayList<>();
if (nums == null || nums.length <=2) {
return ans;
}
Arrays.sort(nums);//O(nlogn)
for (int i = 0; i <nums.length-2 ; i++) {//O(n^2)
if (nums[i]>0) {
break;//第一个数大于0，后面的数都比他大，肯定不成立
}
if (i>0 && nums[i] == nums[i-1]) {
continue; //去掉重复的情况
}
int target = -nums[i];
int left = i+1, right = nums.length-1;
while(left<right){
if (nums[left]+nums[right]==target){
ans.add(new ArrayList<>(Arrays.asList(nums[i],nums[left],nums[right])));
//现在要增加left，减小right，但是不能重复，比如: [-2, -1, -1, -1, 3, 3, 3], i = 0, left = 1, right = 6, [-2, -1, 3] 的答案加入后，需要排除重复的 -1 和 3
left++;right--;// 首先无论如何先要进行加减操作
while (left<right && nums[left] == nums[left-1]) {
left++;
}
while (left<right && nums[right] == nums[right+1]) {
right--;
}
}else if (nums[left] + nums[right]<target){
left++;
}else {//nums[left] +nums[right] >target
right--;
}
}
}
return ans;
}
}
