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不是，用的时间长了好像次序也会乱，保证不了。