15. 三数之和

红太狼 2023-01-01 04:00 106阅读 0赞

# [15. 三数之和][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、代码思路 ##

**暴力匹配**

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

--------------------

**排序 + 双指针**

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

--------------------

**总结：**

1.  题目要求不可以包含重复的三元组，我们可以使用模式识别，利用排序避免重复答案
2.  将数组排序后，进入第一层 `for` 循环之后其实就是 `twoSum` 问题，与 `twoSum` 不同的是，`twoSum` 只需要找到一组解，而这里要找到所有解 ，从而将问题变为：在一个排序数组中找到所有的两数之和
3.  在一个排序数组中找到所有的两数之和：两个指针分别指向数组的首位，如果 `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;
        }
    }

[15.]: https://leetcode-cn.com/problems/3sum/