15.三数之和

难度：中等

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

3 <= nums.length <= 3000
-10^(5) <= nums[i] <= 10^(5)

解题思路

暴力做法是：三重循环获取到目标三元组，再对三元组进行去重操作，但是这样的做法，时间复杂度也太高了，O(n^3) 起步，肯定会超时。

那么简化一点，结合 1. 两数之和 这道题可知，双重 for 循环就可以确定 a 和 b 的值了，再用哈希表来确定 0 - (a + b) 是否在数组里出现过，同时要考虑到题目中说不包含重复的三元组。

如果把目标三元组全部放进 List 中，然后再去重，这样是非常费时的，很容易超时，也是这道题目通过率如此之低的根源所在。

时间复杂度可以做到 O(n^2)，但还是比较费时的，因为不好做 剪枝、去重 的操作。

我的思路：

先对 nums 数组进行升序排序，在排序的数组中，重复的元素会排列在一起，这使得在遍历数组时更容易跳过重复的元素，从而避免在结果中出现重复的三元组，时间复杂度为 O(nlogn)
设定 result 列表用来存储目标三元组
设定哈希表 map 对数组中的元素和位置进行保存，key 为元素值，value 为该元素的 最新下标 ，因为元素会重复，但是 数组已经排了序，所以可以让后者的下标覆盖前者，时间复杂度为 O(n)
双重循环，寻找 nums[i] + nums[j]
- 注意，这里数组排了序，所以当 nums[i-1] == nums[i] 时，如果已经操作过 nums[i-1] 了，就不用再操作 nums[i] 了，这样可以实现剪枝的操作
- 同时，若 nums[i] > 0，那么 nums[j] 肯定也大于0，第三个值肯定也大于0，就更不可能凑成三元组了，此时可以直接退出循环，这也是剪枝操作
- 同理，nums[j] 也可以用同样的方法剪枝，这样可以节省不少时间
- 令 target = - nums[i] - nums[j]，便可以直接在 map 中寻找 target 的下标，如果 target 的坐标大于 j（j 一定是大于 i 的），说明该下标是合法的，我们就可以得到目标三元组
- 收集目标三元组
返回 result 列表

我的代码

java

public List<List<Integer>> threeSum(int[] nums) {
    // 双基准快排算法，对数组进行排序
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    // 使用哈希表记录每个数字最后一次出现的索引
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
	// 遍历数组，寻找所有可能的三元组（a + b + c = 0）
    for (int i = 0; i < nums.length - 2; i++) {
        // 排序之后如果三元组内的 a 已经大于零，那么 b、c 更不可能凑成三元组，直接退出循环
        if (nums[i] > 0) {
            break;
        }
        // 跳过重复的数字 a，避免重复计算相同的三元组
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        for (int j = i + 1; j < nums.length - 1; j++) {
            // 跳过重复的数字 b，避免重复计算相同的三元组
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                continue;
            }
            // 计算两数之和的相反数，寻找这个数是否存在于哈希表中
            int target = - nums[i] - nums[j];
            // 检查哈希表中是否有这个数，且这个数的索引大于j（避免重复使用相同的元素）
            if (map.containsKey(target) && map.get(target) > j) {
                // 找到有效的三元组，加入结果列表
                result.add(Arrays.asList(nums[i], nums[j], target));
            }
        }
    }
    return result;
}

时间复杂度: O(n^2)

空间复杂度: O(n)，额外的 HashMap 开销

双指针做法

思路解析

其实这道题目使用哈希法不是特别合适，因为在去重、剪枝的操作中需要注意很多细节，在面试中很难直接写出没有 bug 的代码。

而且使用哈希法和两层 for 循环的时候，能做的剪枝操作很有限，虽然时间复杂度降到了 O(n^2)，但是程序的执行时间依然比较长：

解答成功:
	执行耗时:122 ms,击败了8.92% 的Java用户
	内存消耗:50.3 MB,击败了22.64% 的Java用户

其实这道题目使用双指针法，要比哈希法高效一些。

当处理的是有序数组时，双指针法特别有用，它依赖于元素的顺序来移动指针。

具体思路：

先对 nums 数组进行升序排序，时间复杂度为 O(nlogn)
设定 result 列表用来存储目标三元组
一层 for 循环，i 从下标 0 的地方开始遍历，同时对 nums[i] 进行去重
设定指针 left 初始指向 i+1 的位置，指针 right 初始指向数组尾端
在数组中找到 nums[i]、nums[left]、nums[right]
- 若 nums[i] + nums[left] + nums[right] == 0 ，则收集目标三元组，并对 nums[left] 和 nums[right] 进行去重
- 若 nums[i] + nums[left] + nums[right] > 0 说明此时三数之和偏大，因为数组已经排序过了，所以 right 下标就应该向左移动，这样才能让三数之和小一些
- 若 nums[i] + nums[left] + nums[right] < 0 说明此时三数之和偏小，left 就应该向右移动，才能让三数之和大一些
- 当 left 与 right 相遇的时候，i 往后遍历
返回 result 列表

代码展示

java

public List<List<Integer>> threeSum(int[] nums) {
    //双基准快排算法
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    // 找出a + b + c = 0
    // a = nums[i], b = nums[left], c = nums[right]
    for (int i = 0; i < nums.length; i++) {
        // 排序之后如果三元组内的a已经大于零，那么b、c更不可能凑成三元组，直接退出循环
        if (nums[i] > 0) {
            break;
        }
        // 去重 a，跳过重复元素
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        // 使用双指针法
        int left = i + 1;
        int right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum > 0) {
                right--;
            } else if (sum < 0) {
                left++;
            } else if (sum == 0) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                // 找到一个三元组之后，对b和c去重
                while (left < right && nums[right - 1] == nums[right]) {
                    right--;
                }
                while (left < right && nums[left + 1] == nums[left]) {
                    left++;
                }    
                // 找到答案时，双指针需要同时收缩
                right--;
                left++;
            }
        }
    }
    return result;
}

时间复杂度: O(n^2)

空间复杂度: O(1)

测试显示，这种算法比哈希法省时很多：

解答成功:
	执行耗时:28 ms,击败了91.35% 的Java用户
	内存消耗:48.9 MB,击败了91.19% 的Java用户

总结

什么时候使用哈希法：

当我们需要快速查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

本题，我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value 结构来存放，key 来存元素，value 来存下标，那么使用 map 正合适。

使用数组和 set 来做哈希法的局限：

数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set 是一个集合，里面放的元素只能是一个 key，而本题，不仅要判断 y 是否存在而且还要记录 y 的下标位置，因为要返回 x 和 y 的下标。所以 set 也不能用。

15.三数之和 ​

解题思路 ​

我的代码 ​

双指针做法 ​

思路解析 ​

代码展示 ​

总结 ​