两数之和 的题目是:
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
首先想到的就是暴力的解法，两层循环遍历数组两次，找到和为目标值target的两个数，返回下标。代码如下：
public 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 };
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
在 leetcode 提交代码后运行时间 35ms 左右，因为用的是笨办法，遍历两次数组的时间复杂度是O(n^2)，耗时会随着数组大小的增大而指数增加。
后来发现用 map 存储一下数据的话，可以做到 O(n) 的时间复杂度。思路就是把数组的每个 item 的值作为 key，对应的下标作为 value 存入 map，这样每次存之前都先算出当前数组 item 的值和 target 的差值作为待查的 key， 让 map 查找这个 key 是否存在，存在即找到正确的结果，取出对应 key 的 value 和当前遍历的 index 返回就行。
因为利用 HashMap 查找 key 理想情况下为 O(1) 的时间复杂度的特性，只用遍历一遍数组就能完成任务，所以时间复杂度是 O(n)。代码如下：
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
int sub = target - nums[i];
if(map.containsKey(sub)){
return new int[]{map.get(sub), i};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
提交后耗时6ms。
思路重点：
关键就在于对于 map 的运用，对于 hash 函数的理解，想要最快速确定集合中元素是否存在，要能有意识的想到 map。
