15. 三数之和

1、参考资料

https://leetcode-cn.com/problems/3sum/

https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/

2、题目要求

题目要求：

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0，请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

3、代码思路

暴力匹配

暴力匹配可以，三层 for 循环带给我们的是 O(n3) 的复杂度，我们还需要将三个数按照从小到大的顺序排列，并使用 HashMap 进行去重操作，得到不包含重复三元组的最终答案
因为 (a, b, c)、(b, a, c)、(b, c, a) 属于重复的三元组，匹配之后我们需要进行排序、去重操作

排序 + 双指针

我们首先要理解不重复的本质是什么？我们先将数组排序，然后在数组中找出三个数 a、b、c，满足其和：a + b + c = 0，其中 a <= b <= c，这样保证了只有 (a, b, c) 这样的顺序，不会出现 (b, a, c) 或者 (b, c, a) 这样的顺序，这样我们就不用对三元组进行去重操作
但是这样做我们始终没有跳出三层 for 循环的思想，实际上第二重 + 第三重循环我们可以使用一层 while 循环 + 双指针来替代
left = i + 1 为左指针(i 最外层 for 循环的计数器)，right = nums.length - 1 为右指针。当 left 增加，right 不变时，三数之和增大；当 right 减小，left 不变时，三数之和减小；我们利用这个特点，可以将原来两层 for 循环变为一层 while 循环，即我们可以通过双指针的方式将内层循环的复杂度从 O(n2) 降为 O(n)
为了保证得到的三元组为不重复的三元组，对于数 a，我们每次在 for 循环中都判断数 a 是否与上次的值相同，如果相同，则跳过本次循环，对于 left 和 right，我们每次在外层 for 开始时，将 left 重置为 i + 1，将 right 重置为 nums.length - 1，在匹配到三数之和等于 0 时，将 left 右移至与上次元素值不同的位置，将 right 左移至与上次元素值不同的位置(保证三元组不重复)

总结：

题目要求不可以包含重复的三元组，我们可以使用模式识别，利用排序避免重复答案
将数组排序后，进入第一层 for 循环之后其实就是 twoSum 问题，与 twoSum 不同的是，twoSum 只需要找到一组解，而这里要找到所有解，从而将问题变为：在一个排序数组中找到所有的两数之和
在一个排序数组中找到所有的两数之和：两个指针分别指向数组的首位，如果 sum > target，那么首指针后移，使得 sum 增大；如果 sum < target，那么尾指针前移，使得 sum 减小

4、代码实现

代码

/**
 * @ClassName ThreeSumDemo
 * @Description TODO
 * @Author Heygo
 * @Date 2020/9/2 17:11
 * @Version 1.0
 */
public class ThreeSumDemo {
    public static void main(String[] args) {
        List<List<Integer>> res = threeSum(new int[]{
    -1, 0, 1, 2, -1, -4});
        System.out.println(res);
    }
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        // Guard Safe
        if (nums == null || nums.length <= 2) {
            return result;
        }
        // 先对数组进行排序，后面才能方便地进行判断是否重复
        Arrays.sort(nums);
        // 遍历数组，当 i = nums.length - 3时，left = nums.length - 2，right = nums.length - 1，为临界条件
        for (int i = 0; i < nums.length - 2; i++) {
            // 如果当前元素大于 0，证明已经将数组中三数之和等于 3 的元素都找出来了，直接跳出循环
            if (nums[i] > 0) {
                break;
            }
            // 上一次的元素和当前相同，跳过此次循环
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int target = -nums[i]; // 目标值
            int left = i + 1; // left 指针
            int right = nums.length - 1; // right 指针
            // 当 left < right 时，证明还有元素待验证
            while (left < right) {
                if (nums[left] + nums[right] == target) {
                    // 如果三数之和等于 0，则将这三个数加入集合中
                    result.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 (nums[left] + nums[right] < target) {
                    // 否则三数之和小于目标值，则 left++，尝试增大三数之和
                    left++;
                } else {
                    // 否则三数之和大于目标值，则 right--，尝试减小三数之和
                    right--;
                }
            }
        }
        return result;
    }
}