题目：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例： 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
本题设计知识点：哈希表
散列表也叫哈希表，这种数据结构提供了键(Key)和值(Value)的映射关系，只要给出一个Key，就可以高效查找其所匹配的value；散列表的本质也是一个数组，而散列表的key是以字符串类型为主 通过某种方式，把key和数组下标进行转换，这个中转站叫做哈希函数。不同语言中，哈希函数的实现方式是不一样的，java的hashmap实现方式：在java中每一个对象都有属于自己的hashcode，这个hashcode是区分不同对象的重要标识，无论对象自身的类型是什么，它们的hashcode都是一个整型变量最简单的转换方式是按照数组长度进行取模运算 index=hashcode(key)%array.length实际上，jdk中的哈希函数并没有直接采用取模运算，而是利用位运算来优化性能。 哈希表的写操作 通过哈希函数，将key转换为数组下标index如果该下标对应位置没有元素，则把entry(键值对)填充到数组下标index的位置哈希冲突后的两种解决方法: 开放寻址法 在java中threadlocal所使用的就是开放寻址法链表法 在java中集合类hashmap就是采取这种方法 哈希表的读操作 通过哈希函数，把key转换成数组下标index在数组下标index中对应元素。 哈希表的扩容 散列表是基于数组实现的，那么散列表也要设计扩容问题。散列表什么时候需要扩容呢？ 当经过多次元素插入，散列表达到一定饱和度时，key映射位置发生冲突的概率会逐渐提高，这样一来，大量元素拥挤到相同数组的下标位置，形成很长的链表，对后续插入和查询操作性能都有很大影响对于jdk中的散列表实现hashmap，影响其扩容的因素有两个： capacity：即hashmap的当前长度loadfactor：即hashmap的负载因子，默认值为0.75f衡量hashmap需要进行扩容的条件如下。 hashmap.size>=capactiyxloadfactor 扩容具体做了如下两件事： 扩容，创建一个新的entry空数组重新hash，遍历原entry数组，将所有entry重新hash到新数组中 HashMap的实现方式中JDK 8 和之前的版本有着很大不同，多个entry被哈希到同一个数组下标位置时，为了提升插入和查找效率，hashmap把entry的链表转换为红黑树的结构 public class leetcode1 { public int[] twoSum(int[] nums, int target) { if (nums==null || nums.length<2){ return nums; } int[] res = new int[2]; int length = nums.length; // 第一种方法：双重循环 // for (int i=0;i<length-1;i++){ // for (int j=i+1;j<length;j++){ // if (nums[i]+nums[j]==target){ // res[0] = i; // res[1] = j; // return res; // } // } // } // 第二种方法，哈希表 HashMap<Integer,Integer> hashMap = new HashMap<>(); for (int i=0;i<length;i++){ if (hashMap.containsKey(target-nums[i])){ res[0] = hashMap.get(target-nums[i]); res[1] = i ; return res; } hashMap.put(nums[i],i); } return res; } }