题目：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
最简单，也最容易的就是double for循环，但是时间复杂度太高了，是O(n^2)；
其实，思维变换一下，我们是要在数组中找一个num 和 target -num的值，那我们可以搞成两个数组，第一个是原始数据nums1，第二个是target-num的数据nums2，这样的话，就变成了怎么在nums2数组中找到和nums1中相同的数，比如nums1 = {1,3,5,7,9}，target=6；nums2={5,3,1,-1,-3}；可以明显看出来，1,3,5在nums2中也存在，去除掉3(自身)，就是1,5了。
那么怎么快速在nums2中找到是否存在和nums1中相同的值呢，使用Hash表。
代码实现一：
- 先把nums数组中值和索引存到HashMap中
- 循环nums数组，查找是否存在target-num的key，同时找到的key不能是自身
- 输出数组当前索引i，和找到值key对应的vlaue(目标索引)
import java.util.HashMap;
import java.util.Map;
public class twoSum {
public static void main(String[] args) {
int nums[] = {1,2,3,4,5};
int target = 6;
twoSum1(nums,target);
}
public static void twoSum1(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i],i);
}
for(int i=0;i< nums.length;i++){
int temp = target-nums[i];
if(map.containsKey(temp) && map.get(temp)!=i){
System.out.println(i+"==="+ map.get(temp));
}
}
}
代码实现二：
代码实现一其实会有数据重复的问题，比如会出现{1,5} 和 {5,1}，下面的实现二不仅避免了重复问题，还是只循环了nums一次，降低了时间复杂度，从O(2n)降到了O(n)
import java.util.HashMap;
import java.util.Map;
public class twoSum {
public static void main(String[] args) {
int nums[] = {1,2,3,4,5};
int target = 6;
twoSum2(nums,target);
}
public static void twoSum2(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int temp = target-nums[i];
if(map.containsKey(temp) && map.get(temp)!=i){
System.out.println(i+"==="+ map.get(temp));
}
map.put(nums[i],i);
}
}
}
