twoSum问题的核心思想

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

TwoSum I

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

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

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

  1. int[] twoSum(int[] nums, int target) {
  2. for (int i = 0; i < nums.length; i++)
  3. for (int j = i + 1; j < nums.length; j++)
  4. if (nums[j] == target - nums[i])
  5. return new int[] { i, j };
  6. // 不存在这么两个数
  7. return new int[] {-1, -1};
  8. }

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

可以通过一个哈希表减少时间复杂度:

  1. int[] twoSum(int[] nums, int target) {
  2. int n = nums.length;
  3. index<Integer, Integer> index = new HashMap<>();
  4. // 构造一个哈希表:元素映射到相应的索引
  5. for (int i = 0; i < n; i++)
  6. index.put(nums[i], i);
  7. for (int i = 0; i < n; i++) {
  8. int other = target - nums[i];
  9. // 如果 other 存在且不是 nums[i] 本身
  10. if (index.containsKey(other) && index.get(other) != i)
  11. return new int[] {i, index.get(other)};
  12. }
  13. return new int[] {-1, -1};
  14. }

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

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

TwoSum II

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

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

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

  1. class TwoSum {
  2. Map<Integer, Integer> freq = new HashMap<>();
  3. public void add(int number) {
  4. // 记录 number 出现的次数
  5. freq.put(number, freq.getOrDefault(number, 0) + 1);
  6. }
  7. public boolean find(int value) {
  8. for (Integer key : freq.keySet()) {
  9. int other = value - key;
  10. // 情况一
  11. if (other == key && freq.get(key) > 1)
  12. return true;
  13. // 情况二
  14. if (other != key && freq.containsKey(other))
  15. return true;
  16. }
  17. return false;
  18. }
  19. }

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

情况一:add[3,3,2,5] 之后,执行 find(6),由于 3 出现了两次,3 + 3 = 6,所以返回 true。

情况二:add[3,3,2,5] 之后,执行 find(7),那么 key 为 2,other 为 5 时算法可以返回 true。

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

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

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

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

  1. class TwoSum {
  2. Set<Integer> sum = new HashSet<>();
  3. List<Integer> nums = new ArrayList<>();
  4. public void add(int number) {
  5. // 记录所有可能组成的和
  6. for (int n : nums)
  7. sum.add(n + number);
  8. nums.add(number);
  9. }
  10. public boolean find(int value) {
  11. return sum.contains(value);
  12. }
  13. }

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

三、总结

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

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

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

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

  1. int[] twoSum(int[] nums, int target) {
  2. int left = 0, right = nums.length - 1;
  3. while (left < right) {
  4. int sum = nums[left] + nums[right];
  5. if (sum == target) {
  6. return new int[]{left, right};
  7. } else if (sum < target) {
  8. left++; // 让 sum 大一点
  9. } else if (sum > target) {
  10. right--; // 让 sum 小一点
  11. }
  12. }
  13. // 不存在这样两个数
  14. return new int[]{-1, -1};
  15. }

坚持原创高质量文章,致力于把算法问题讲清楚,欢迎关注我的公众号 labuladong 获取最新文章:

labuladong

上一篇:滑动窗口技巧

下一篇:常用的位操作

目录