LeetCode 15.三数之和

一、题目

二、解题

注：本文均是Java代码

1、相向双指针

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 不重复的三元组，输出三元组的顺序不重要
        // 数组如果有序可以使用相向双指针
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            int x = nums[i];
            if (i > 0 && nums[i] == nums[i-1]) continue;
            int j = i + 1, k = n - 1;
            while (j < k) {
                int sum = x + nums[j] + nums[k];
                if (sum < 0) j++;
                else if (sum > 0) k--;
                else {
                    List<Integer> res = new ArrayList<>();
                    res.add(x); res .add(nums[j]); res.add(nums[k]);
                    result.add(res);
                    j++;
                    while (j < k && nums[j] == nums[j-1]) j++;
                    k--;
                    while (j < k && nums[k] == nums[k+1]) k--;
                }   
            }
        }
        return result;
    }
}

2、优化版本

做两个小优化。如果前三个数，也就是最小的三个数的和都大于0，那么可以直接结束循环，根本不存在等于0的三元组。如果x加上最后两个数的和都小于0，那么结束当次循环，这次循环不会有等于0的三元组，需要i++继续寻找。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 时间复杂度O(n^2)，排序的忽略
        // 空间复杂度O(1)
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        // 注意n的范围，否则可能数组越界
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            int x = nums[i];
            // 注意这不能是while，否则可能数组越界
            if (i > 0 && nums[i] == nums[i-1]) continue;
            if (nums[i] + nums[i+1] + nums[i+2] > 0) break;    // 优化一
            if (nums[i] + nums[n-2] + nums[n-1] < 0) continue;    // 优化二
            int j = i + 1, k = n - 1;
            while (j < k) {
                int sum = x + nums[j] + nums[k];
                if (sum < 0) j++;
                else if (sum > 0) k--;
                else {
                    List<Integer> res = new ArrayList<>();
                    res.add(x); res .add(nums[j]); res.add(nums[k]);
                    result.add(res);
                    j++;
                    // 注意这不能是if，否则有的重复数没有检索到加入到循环，有重复
                    while (j < k && nums[j] == nums[j-1]) j++;
                    k--;
                    while (j < k && nums[k] == nums[k+1]) k--;
                }   
            }
        }
        return result;
    }
}

3、说明

参考视频：两数之和 三数之和【基础算法精讲 01】_哔哩哔哩_bilibili