16 | 面试题：三数之和

题目：

15. 三数之和

解法一：暴力

3层嵌套的枚举，时间复杂度：O(N³)，有多种结果，需要都保存。（需要考虑去重，则实际上看解法三更容易）

解法二：像两数之和一样，使用辅助数据结构。枚举 a，b，枚举完后去数组中查找 -(a+b) 是否存在即可。

查询时可使用 SET 数据结构，查询时 O(1)。枚举 a，b 是两层循环。

时间复杂度：O(N²) = 排序 + 枚举(N*N) + SET 转 LIST = 总时间复杂度O(N²)

空间复杂度：O(N) = 数组(N) + MAP(N) = O(2N) = O(N)

总体上忽略常数类似，但明显慢于方法三的暴力双指针，逻辑上也更复杂。不推荐。

class Solution {
    fun threeSum(nums: IntArray): List<List<Int>> {
        val n = nums.size
        //排序去重
        Arrays.sort(nums)
        //Hash去重
        val ans = HashSet<List<Int>>()

        for (first in 0 until n) {
            //过滤和上次不同
            if (first > 0 && nums[first] == nums[first - 1]) continue
            //两数之和处理方式
            val map = HashMap<Int, Int>()

            for (second in first + 1 until n) {
                val complement = -nums[first] - nums[second]  //third 值
                if (map.containsKey(complement)) {
                    //顺序问题需要处理 和两数之和一样
                    ans.add(listOf(nums[first], nums[map[complement]!!], nums[second]))
                } else {
                    map[nums[second]] = second
                }
            }
        }
        return ans.toList()
    }
}

解法三：暴力 + 双指针

这个会改变原输入数据，或者重新拷贝一次数据源（冗余）。

思路：整个数组排序 – 快排，时间复杂度O(NlogN)，然后枚举一个元素，比如 a。在剩下的数组中找 b，c 即可。如何查找？由于已经排序，此时使用双指针从两端开始向中间查找，然后判断a + b + c，如果是大于0的，说明右指针需要往左移动，小于0的则说明左指针需要往右移动。

附加优化处理：

去重问题解决：先排序，然后枚举时如果与上一个元素相同则跳过。

最后一次查找优化：使用指针，从右往左寻找，相当于均分查找次数。

时间复杂度：O(N²) = 枚举一个元素 O(N) * 查找 O(N) ，N 是数组长度。

空间复杂度：官方说类似 O(log N)，但我更倾向于 O(N)。

class Solution {
    fun threeSum(nums: IntArray): List<List<Int>> {
        val n = nums.size
        Arrays.sort(nums)

        val ans = mutableListOf<List<Int>>()

        for (first in 0 until n) {
            //过滤和上次不同
            if (first > 0 && nums[first] == nums[first - 1]) continue
            //从右开始
            var third = n - 1
            val target = 0 - nums[first]
            for (second in first + 1 until n) {
                //过滤和上次不同
                if (second > first + 1 && nums[second] == nums[second - 1]) continue
                //保证不越界 然后确定元素位置
                while (second < third && nums[second] + nums[third] > target) third--
                //指针重合，条件不成立
                if (second == third) break
                //找到则添加
                if (nums[second] + nums[third] == target) {
                    ans.add(listOf(nums[first], nums[second], nums[third]))
                }
            }
        }
        return ans
    }
}

老师说解法二更优，可以不动原数组，但在实际去重中，处理的逻辑更复杂。这里不做深入探索。实际中，具体问题具体分析。

后面还给了两道题：

18. 四数之和

49. 字母异位词分组