题目描述：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目分析：
题目中有以下条件是我们正确解答题目的关键：
- “假设每种输入只会对应一个答案”，说明数组中如果有重复数字并且重复数字是答案的一部分，那么重复数字有且仅有两个并且这两个就是答案，如：
给定 nums = [3, 3, 1, 9], target = 6
因为 nums[0] + nums[1] = 3 + 3 = 6
所以返回 [0, 1]
- “不能重复利用这个数组中同样的元素”，无法使用双层循环这样的暴力解法。
解答：
为了便于说明我们还是先使用暴力解法：
使用双层循环，第一层循环找到当前值与目标值的差值tempJ。第二层循环寻找tempJ是否存在,如果存在则返回其位置
public int[] twoSum(int[] nums, int target) {
int i = 0, j = 0;
for (; i < nums.length; i++) {
int tempJ = target - nums[i];
j = getNumJ(nums,tempJ,i);
if(j != -1 ){
break;
}
}
return new int[]{i, j};
}
/**
* @param nums
* @param tempJ
* @param i
* @return 如何元素存在则返回元素的位置，否则返回-1
*/
private int getNumJ(int[] nums, int tempJ ,int i) {
for (int j = i+1; j < nums.length; j++) {
if(nums[j] == tempJ){
return j;
}
}
return -1;
}
我们可以看到在上述解法的时候，找tempJ的时候元素被使用了多次，我们应当寻找快速定位到tempJ的方式；我们可以想到利用HashMap来存储数据，从而快速定位。
最终我们得到的解决方案如下：
public class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> numMap = new HashMap<>();
int i = 0, j = 0;
for (; i < nums.length; i++) {
int tempJ = target - nums[i];
Integer position = numMap.get(tempJ);
if(position != null){
j = position;
break;
}
numMap.put(nums[i],i);
}
return new int[]{j, i};
}
}
那么HashMap在get数据难道不是通过遍历的方式么？当然不是，HashMap是Java中较为基础的数据接构，感兴趣的同学可以去阅读下源码。这里简单的说明下他是如何通过hash存储和取值的。
在jdk1.8之前hashmap是使用数组+链表的形式存储的，数据结构如下图
当我们向该数据结构中存键值对（key-value）时，会获取“key”的hashCode（不同类型key的hashCode的生成方式可以参看该类的hashCode方法，如Integer的hashCode为Integer的value），获取到的每一个hashCode对应数组上的一个位置，插入的时候直接将value放到该位置上，如果当前位置不为空，则直接放到该位置对应的链表中。至于取值的方式就显而易见了，直接获取key的hashCode，找到它在数组中的位置，获取该位置的值即可，如果当前位置的key不是我们想要的那个key，则需要遍历该位置对应的链表获取到对应的值。到这里你可能会说，这里还是会遍历，是否能满足只遍历一次数据的需求？当然能，理由在“题目分析”的第一点已经说了，我们需要的答案的数据最多只有两个重复的，并且我们在找j的时候，j还没有被插入，因此不会存在hash冲突，不需要遍历。
