15. 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：

输入：nums = []
输出：[]
示例 3：

输入：nums = [0]
输出：[]
 

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

解题思路

暴力解法：如果直接采用三层for循环，然后去遍历，找到三个元素，然后通过hashset或者自定义类，来去重，这样肯定超时
1.我们需要去想一下，如何优化算法，条件是a+b+c=0，其实我们可以优化为找到a+b=-c
2.三层for循环是根本，第一层和第二层循环不可避免，第三层需要可以利用a+b==-c的点来优化
3.如何优化？我们想到这个是一个整数数组，如果我把它排序之后，其实第二层遍历和第三层遍历，完全可以使用双指针方案来优化
4.第三层for循环，可以优化为一个k指针（默认位置为int k = nums.length - 1），有一个k指针从后往前，找寻nums[j] + nums[k] == nums[i]的元素
5.如果k--，一直往前找，依然无法找到，则无法找到
6.如果有满足的元素，则这时为结果元素
7.还剩余一个问题，如何去重?题目中要求我们不能有重复元素，也是利用数组已排序的点，如果数组排序之后，遍历过程中发现和前一个元素相同，则实际上就是重复了

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    /**
     * 解题思路
     * 暴力解法：如果直接采用三层for循环，然后去遍历，找到三个元素，然后通过hashset或者自定义类，来去重，这样肯定超时
     * 1.我们需要去想一下，如何优化算法，条件是a+b+c==0，其实我们可以优化为找到a+b==-c
     * 2.三层for循环是根本，第一层和第二层循环不可避免，第三层需要可以利用a+b==-c的点来优化
     * 3.如何优化？我们想到这个是一个整数数组，如果我把它排序之后，其实第二层遍历和第三层遍历，完全可以使用双指针方案来优化
     * 4.第三层for循环，可以优化为一个k指针（默认位置为int k = nums.length - 1），有一个k指针从后往前，找寻nums[j] + nums[k]  == nums[i]的元素
     * 5.如果k--，一直往前找，依然无法找到，则无法找到
     * 6.如果有满足的元素，则这时为结果元素
     * 7.还剩余一个问题，如何去重?题目中要求我们不能有重复元素，也是利用数组已排序的点，如果数组排序之后，遍历过程中发现和前一个元素相同，则实际上就是重复了
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> target = new ArrayList<List<Integer>>();
        if (nums == null || nums.length < 2) {
            return target;
        }

        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            // 需要和上一次枚举的数不相同
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < nums.length; j++) {
                // 需要和上一次枚举的数不相同
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                
                int temp = -nums[i];
                int k = nums.length - 1;
        
                while (nums[j] + nums[k] > temp && j < k) {
                    k--;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (j == k) {
                    break;
                }

                if (nums[i] + nums[j] + nums[k] == 0) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    target.add(list);
                }
            }
        }
        return target;
    }
}