设计的核⼼在于权衡，利⽤不同的数据结构，可以得到⼀些针对性的加强。
⼀般情况下，我们会⾸先把数组排序再考虑双指针技巧。受 TwoSum 启发，HashMap 或者 HashSet 也可以帮助处理⽆序数组相关的简单问题。
twoSum I
给定⼀个数组和⼀个整数 target ，可以保证数组中存在两个数的和为 target ，请返回这两个数的索引
利用哈希表解法：
1
2
3
4
5
6
7
8
9
10
11
12
13
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
Map<Integer, Integer> index = new HashMap<>();
// 构造⼀个哈希表：元素映射到相应的索引
for (int i = 0; i < n; i++) {
int other = target - nums[i];
// 如果 other 存在且不是 nums[i] 本⾝
if (index.containsKey(other))
return new int[]{i, index.get(other)};
index.put(nums[i], i);
}
return new int[]{-1, -1};
}
由于哈希表的查询时间为 O(1)，算法的时间复杂度降低到 O(N)，但是需要 O(N) 的空间复杂度来存储哈希表。
twoSum II
设计⼀个类，拥有两个 API：
1
2
3
4
5
6
class TwoSum {
// 向数据结构中添加⼀个数 number
public void add(int number);
// 寻找当前数据结构中是否存在两个数的和为 value
public boolean find(int value);
}
实现一：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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;
}
}
对于这个解法的时间复杂度呢， add ⽅法是 O(1)， find ⽅法是 O(N)，空间复杂度为 O(N)。
实现二：
1
2
3
4
5
6
7
8
9
10
11
12
13
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 的场景。
