读完本文,你能够去力扣拿下如下题目:
1. 两数之和
170. 两数之和 III – 数据结构设计
———–
Two Sum 系列问题在 LeetCode 上有好几道,这篇文章就挑出有代表性的几道,介绍一下这种问题怎么解决。
TwoSum I
这个问题的 最根本模式 是这样:给你一个数组和一个整数 target
,能够保障数组中 存在 两个数的和为 target
,请你返回这两个数的索引。
比方输出 nums = [3,1,3,6], target = 6
,算法应该返回数组 [0,2]
,因为 3 + 3 = 6。
这个问题如何解决呢?首先最简略粗犷的方法当然是穷举了:
int[] twoSum(int[] nums, int target) {for (int i = 0; i < nums.length; i++)
for (int j = i + 1; j < nums.length; j++)
if (nums[j] == target - nums[i])
return new int[] { i, j};
// 不存在这么两个数
return new int[] {-1, -1};
}
这个解法十分间接,工夫复杂度 O(N^2),空间复杂度 O(1)。
能够通过一个哈希表缩小工夫复杂度:
int[] twoSum(int[] nums, int target) {
int n = nums.length;
index<Integer, Integer> index = new HashMap<>();
// 结构一个哈希表:元素映射到相应的索引
for (int i = 0; i < n; i++)
index.put(nums[i], i);
for (int i = 0; i < n; i++) {int other = target - nums[i];
// 如果 other 存在且不是 nums[i] 自身
if (index.containsKey(other) && index.get(other) != i)
return new int[] {i, index.get(other)};
}
return new int[] {-1, -1};
}
这样,因为哈希表的查问工夫为 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
办法:
class TwoSum {Map<Integer, Integer> freq = new HashMap<>();
public void add(int number) {
// 记录 number 呈现的次数
freq.put(number, freq.getOrDefault(number, 0) + 1);
}
public boolean find(int value) {for (Integer key : freq.keySet()) {
int other = value - key;
// 状况一
if (other == key && freq.get(key) > 1)
return true;
// 状况二
if (other != key && freq.containsKey(other))
return true;
}
return false;
}
}
进行 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
办法:
class TwoSum {Set<Integer> sum = new HashSet<>();
List<Integer> nums = new ArrayList<>();
public void add(int number) {
// 记录所有可能组成的和
for (int n : nums)
sum.add(n + number);
nums.add(number);
}
public boolean find(int value) {return sum.contains(value);
}
}
这样 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};
}