力扣---15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：
    3 <= nums.length <= 3000
    -105 <= nums[i] <= 105

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一开始对暴力法做了些剪枝优化，结果还是运行超时。之后使用了双指针，由于刚开始的思路有问题，虽然能做出来，但被数组越界的问题搞得焦头烂额，写了一大堆if，else。在之后学习了下大佬的思路，优化了下写法，终于是做了出来。需要注意到的情况放注释里了。

代码如下：

 1 class Solution {
 2     public List<List<Integer>> threeSum(int[] nums) {
 3         Arrays.sort(nums);
 4         List<List<Integer>> res = new ArrayList<>();
 5         //i < nums.length - 2 是为了避免指针越界。
 6         for (int i = 0; i < nums.length - 2; i ++) {
 7             //如果nums[0] > 0 ，因为已经排好序了，之后的数字也肯定大于0，此时必定不会出现相加等于0的情况。
 8             if (nums[0] > 0) {
 9                 break;
10             }
11             //针对nums[i] 重复出现的情况去重。
12             if (i > 0) {
13                 if (nums[i] == nums[i - 1]) {
14                     continue;
15                 }
16             }
17             //定义指针，保证不会出现 i == p1, i == p2, p1 == p2的情况。
18             //定义左指针
19             int p1 = i + 1;
20             //定义右指针
21             int p2 = nums.length - 1;
22             
23             while (p1 < p2) {
24                 int ans = nums[i] + nums[p1] + nums[p2];
25                 if (ans < 0) {
26                     p1 ++;
27                     //针对nums[p1]重复。
28                     while(p1 < p2 && nums[p1] == nums[p1 - 1]) {
29                         p1 ++;
30                     }
31                 } else if (ans > 0) {
32                     p2 --;
33                     //针对nums[p2]重复。
34                     while (p1 < p2 && nums[p2] == nums[p2 + 1]) {
35                         p2 --;
36                     }
37                 } else {
38                     //之前已经针对nums[i], nums[p1], nums[p2]重复出现的情况去过重了，且由于左右指针的定义，可以确保没有重复值。
39                     res.add(new ArrayList<>(Arrays.asList(nums[i], nums[p1], nums[p2])));
40                     p1 ++;
41                     //针对nums[p1]重复。
42                     while(p1 < p2 && nums[p1] == nums[p1 - 1]) {
43                         p1 ++;
44                     }
45                     p2 --;
46                     //针对nums[p2]重复。
47                     while (p1 < p2 && nums[p2] == nums[p2 + 1]) {
48                         p2 --;
49                     }
50                 }
51             }
52         }
53         return res;
54     }
55 }

运行结果：