题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] = 0 。请你返回所有和为 0 且不重复的三元组。

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

题目分析

哈希表+去重

遍历一次数组，将所有数字放入哈希表，同时记录每个数字的数量
枚举下标 i 和 j，判断哈希表中是否存在数字值为-num[i]-num[j]，且要保证和哈希表记录的数字数量不冲突，存在则放入结果集合中。结果集合要做去重。
时间复杂度O(n^2)

排序+双指针（推荐）

将数组从小到大排序。
枚举下标 i，枚举时要判断是否和 i – 1 重复
将 j 初始化为 i+1，k 初始化为 nums.length - 1
判断三个数字之和 sum：
– 大于0: k 向左移动一位
– 小于0: j 向右移动一位
– 等于0: 放入结果集合中。j++ 或 k-- 都可以，但要保证和调整前的数字不重复

为什么 j 和 k 只能向内侧移动？
思考时要从初始状态思考，而不是直接从中间态思考。
对于初始状态，j 在左边界，k 在右边界。以 sum > 0 为例，对于 k 来说，j 已经是当前数组的最小值，因此无论后续 j 移动到哪里，sum 都会变得更大，此刻 k 对应的数字是无用的，所以可以将它删除。删除后的新数组，j 和 k 依然是左边界和右边界。代码里没必要真的删除，而是限制指针只能向内侧移动。
时间复杂度O(n^2)

Java

public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int j = i + 1;
            int k = nums.length - 1;
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    int p = nums[j];
                    while (j < k && nums[j] == p) {
                        j++;
                    }
                } else if (sum > 0) {
                    k--;
                } else {
                    j++;
                }
            }
        }
        return result;
    }

Kotlin

fun threeSum(nums: IntArray): List<List<Int>> {
        val result = ArrayList<List<Int>>()
        nums.sort()
        for (i in nums.indices) {
            var j = i + 1
            var k = nums.size - 1
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue
            }
            if (nums[i] > 0) {
                break
            }

            while (j < k) {
                val sum = nums[i] + nums[j] + nums[k]
                if (sum == 0) {
                    result.add(arrayListOf(nums[i], nums[j], nums[k]))
                    val p = nums[j]
                    while (j < k && nums[j] == p) {
                        j++
                    }
                } else if (sum > 0) {
                    k--
                } else {
                    j++
                }
            }
        }
        return result
    }