读完本文，你能够去力扣拿下如下题目：
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};}