Two Sum 问题的核心思想

点击蓝色“五分钟学算法”关注我哟

加个“星标”,天天中午 12:15,一起学算法

Two Sum 问题的核心思想

作者 | labuladong

来源 | labuladong

Two Sum 系列问题在 LeetCode 上有好几道,这篇文章就挑出有代表性的两道,介绍一下这种问题怎么解决。

TwoSum I

这个问题的最基本形式是这样:给你一个数组和一个整数target,可以保证数组中存在两个数的和为target,请你返回这两个数的索引。

比如输入nums = [3,1,3,6],target = 6,算法应该返回数组[0,2],因为 3 + 3 = 6。

这个问题如何解决呢?首先最简单粗暴的办法当然是穷举了:

Two Sum 问题的核心思想

这个解法非常直接,时间复杂度 O(N^2),空间复杂度 O(1)。

更好一点的解法,可以通过一个哈希表减少时间复杂度:

Two Sum 问题的核心思想

这样,由于哈希表的查询时间为 O(1),算法的时间复杂度降低到 O(N),但是需要 O(N) 的空间复杂度来存储哈希表。不过综合来看,是要比暴力解法高效的。

我觉得 Two Sum 系列问题就是想教我们如何使用哈希表处理问题。我们接着往后看。

TwoSum II

稍微修改一下上面的问题,要求我们设计一个类,拥有两个 API:

class TwoSum {
    // 向数据结构中添加一个数 number
    public void add(int number);
    // 寻找当前数据结构中是否存在两个数的和为 value
    public boolean find(int value);
}

如何实现这两个 API 呢,我们可以仿照上一道题目,使用一个哈希表辅助find方法:

Two Sum 问题的核心思想

进行find的时候有两种情况,举个例子:

情况一:如果连续 add 了 [3,2,3,5],那么freq{3:2,2:1,5:1},执行find(6),由于 3 出现了两次,3 + 3 = 6,所以返回 true。

情况二:freq{3:2,2:1,5:1},执行find(7),那么key为 2,other为 5 时算法可以返回 true。

除了上述两种情况外,find只能返回 false 了。

对于这个解法的时间复杂度呢,add方法是 O(1),find方法是 O(N),空间复杂度为 O(N),和上一道题目比较类似。

但是对于 API 的设计,是需要考虑现实情况的比如说,我们设计的这个类,使用find方法非常频繁,那么每次都要 O(N) 的时间,岂不是很浪费费时间吗?对于这种情况,我们是否可以做些优化呢?

是的,对于频繁使用find方法的场景,我们可以进行优化。我们可以参考上一道题目的暴力解法,借助哈希集合来针对性优化find方法:

Two Sum 问题的核心思想

这样sum中就储存了所有加入数字可能组成的和,每次find只要花费 O(1) 的时间在集合中判断一下是否存在就行了,显然非常适合频繁使用find的场景。

三、总结

对于 TwoSum 问题,一个难点就是给的数组无序。对于一个无序的数组,我们似乎什么技巧也没有,只能暴力穷举所有可能。

一般情况下,我们会首先把数组排序再考虑双指针技巧。TwoSum 启发我们,HashMap 或者 HashSet 也可以帮助我们处理无序数组相关的简单问题。

另外,设计的核心在于权衡,利用不同的数据结构,可以得到一些针对性的加强。

最后,如果 TwoSum I 中给的数组是有序的,应该如何编写算法呢?答案很简单,前文 双指针技巧汇总 写过:

int[] twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return new int[]{left, right};
        } else if (sum < target) {
            left++; // 让 sum 大一点
        } else if (sum > target) {
            right--; // 让 sum 小一点
        }
    }
    // 不存在这样两个数
    return new int[]{-1, -1};
}


Two Sum 问题的核心思想

有热门推荐👇


1.程序员我们就必须承认:这个世界上,有很多问题,就是无解的

2.【GitHub我在 GitHub 上看到了一个丧心病狂的开源项目!

3.【算法动画:七分钟理解什么是KMP算法

4.【数据结构十大经典排序算法动画与解析,看我就够了!


Two Sum 问题的核心思想

▼ 点击『阅读原文』解锁更多图解 LeetCode 题目

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » Two Sum 问题的核心思想

我还会在以下平台发布内容

GitHub 哔哩哔哩