Q：
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:
Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0, 1].
A：
Brute Force，时间复杂度为O(n^2)。
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length; j++) {
if (nums[i] = target - nums[j]) {
return new int[] {i,j}; //直接new一个新的返回
}
}
}
throw new IllegalArgumentException ("No Match");
}
HashTable，时间复杂度为O(n)。
public int[] twoSum(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 complement = target - nums[i];
// containsKey的复杂度是O(1)，containsValue的复杂度是O(n)
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] { i, map.get(complement) };
}
}
throw new IllegalArgumentException("No two sum solution");
}
单次跑Hashmap，找到就弹出结果，不继续put后面的进Hashmap了。精炼！
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
//第一遍还是空的，什么都不做，下面put一次！
//这个 containsKey 方法返回值是boolean, true if mapping
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
//put先执行一次，别的再说
map.put(nums[i], i); //key和value这里是反着的，因为最后要按index值输出
}
throw new IllegalArgumentException("No two sum solution");
}
Notes：
时间复杂度 计算方法
.
看看有几重for循环，
只一重，为O(n)，
二重，为O(n^2)，
有二分，为O(logn)，
一个for循环套一个二分，为O(nlogn)。
HashTable vs HashMap
.
HashMap比HashTable新，储存键值对象(Key Value)，可以接受null，非synchronized。
没有正确同步的时候，多个线程不能正确共享HashMap。同步方法为：
Map m = Collections.synchronizeMap(hashMap);
.
如果一个类没有重写hash方法，那么就是默认使用Object的hash方法。
.
一个Key只能映射一个Value，赋值同个Key，后来的，覆盖之前的。
Map vs HashMap
.
Map ：是Interface 接口 JAVA API: Class HashMap <Key, Value>
HashMap ：是class 实现类 JAVA API: Interface Map <Key, Value>
只能访问Map定义的方法和属性：
Map map1 = new Hashmap()；
可以访问到HashMap定义的方法和属性：
Map map = (Map)map2； //这又回去了,只能访问Map的了````
Hashmap是子类，它自己定义了一堆方法。
.
Map中要的是对象 <Object, Object>不能使用基本类型（比如int），Integer可以。
如果 map.put (1，“123”)，会自动封装，map.put(new Integer(1), "123");
Java Collection Framework （和Hash相关的）
.
HashSet和HashMap实现的是不同接口。
TreeMap的对象是Sorted，HashMap不是，用的时间长了好像次序也会乱，保证不了。
