【复试上机】LeetCode刷题-简单-1. Two Sum

题目

文字思想：

遍历数组中所有元素，假设当前遍历到到的数是A，下标是i，我们构建HashMap为(期待的加数 = target - A, A)，则A+期待的加数=target。对每一个遍历到的数，我们看看它是否存在与HashMap的key中，如果存在，那么这个数与对应的value就是解。

当然，要求返回的是下标，所以构建HashMap为(期待的加数 = target - A， i)。

例子：

数组：2, 11, 15, 7
目标和：9
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
当前HashMap：
当前处理：2，下标为：0
2不是HashMap的key，我们计算它期待的另一个加数
2期待的另一个加数是：7
HashMap中新增存储项：key=7, value=0
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
当前HashMap：
(7, 0)
当前处理：11，下标为：1
11不是HashMap的key，我们计算它期待的另一个加数
11期待的另一个加数是：-2
HashMap中新增存储项：key=-2, value=1
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
当前HashMap：
(-2, 1)
(7, 0)
当前处理：15，下标为：2
15不是HashMap的key，我们计算它期待的另一个加数
15期待的另一个加数是：-6
HashMap中新增存储项：key=-6, value=2
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
当前HashMap：
(-2, 1)
(-6, 2)
(7, 0)
当前处理：7，下标为：3
7是HashMap的key，那么key=7 + nums[value]= = nums[0]=2 = target = 9
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
对应下标：3,0

代码：

代码

时间复杂度：
​ 遍历nums，O(n)，空间复杂度：HashMap，O(n)。

积累：

1. HashMap机制：key-value，这属于Java知识。
2. 本题完整思想。

推荐阅读：LeetCode刷题集合