1. 2Sum

字典法，将原字典key和value转换，遍历一次数组并返回第一个数字出现的index和当前数字的index。在同一个loop中边记忆数字出现的index，和判断当前补数是否在字典中。

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int j = target - nums[i]; // get the key
        if (map.containsKey(j)) {
            return new int[] {map.get(j), i}; //return stored index and current index
        } else {
            map.put(nums[i], i); // put the current number as key, index as value
            //j <--> nums[i]; map.get(j) <--> i; map(value, index)
        }
    }
    return null;
}

变种：

1. Two Sum II - Input array is sorted，由于排序的特性可以使用双指针