抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

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. 字母异位词分组


0条评论

发表评论