【排序, 双指针】三数之和

## 题目

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
• -10^5 <= nums[i] <= 10^5

解题

方法一：排序 + 双指针

思路

将数组排好序，遍历一个数 nums[i] 使三数之和 ($a + b + c = 0$) 转换为两数之和 ($b + c = -a$)

然后定下左指针 left 初始指向 i+1 表示第二个数，右指针 right 初始指向 nums.length-1 表示第三个数，两个指针向中间移动直至相撞时停止

计算三数之和 sum，由于数组是升序的，则有：

• 当 $sum<0$ 时需要将 sum 增大，故将左指针右移
• 当 $sum>0$ 时需要将 sum 减小，故右指针左移
• 当 $sum=0$ 时 ${nums[i], nums[left], nums[right]}$ 是一组合法的解 这时将三个数字加入结果集中，左右指针继续向中间移动，这时移动的过程中若遇到连续的相同数字，为防止有效解重复，要跳过这些相同的数字

代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        int len = nums.length;
        // 遍历以确定下来一个数
        for (int i = 0; i < len; i++) {
            // 遇到连续的相同数字则跳过
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 初始化左右指针
            int left = i + 1, right = len - 1;
            // 终止条件: 两指针相撞
            while(left < right) {
                // 计算三数之和
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    // 小了 需要增大 左指针右移
                    left++;
                } else if (sum > 0) {
                    // 大了 需要减小 右指针左移
                    right--;
                } else {
                    // 相同 得出一组合法的解
                    ans.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--;
                    }
                }
            }
        }

        return ans;
    }
}

剪枝优化

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        int len = nums.length;
        if (len < 3 || nums[0] > 0 || nums[len - 1] < 0) {
            // 剪枝: 数组长度不够或者数组里元素都大于或都小于0不存在解
            return ans;
        }

        // 剪枝: 第一个数字如果大于0 其与右边两个数字加和的结果不可能是0了
        for (int i = 0; i < len && nums[i] <= 0; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1, right = len - 1;
            while(left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    left++;
                } else if (sum > 0) {
                    right--;
                } else {
                    ans.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--;
                    }
                }
            }
        }

        return ans;
    }
}