1. Two Sum

原题

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, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

题意

给出一个整型数组，返回两个整型数所对应的索引，这两个整型数之和为目标值。

你可以假设每个输出都有且只有一个解决方法，另外一个整型数只能使用一次。

思路

最直接的蛮力法就是通过两层 for 循环组合出两个符合要求的索引 O(n²)。

其实，每当为第一层 for 循环的迭代数，在第二层 for 循环中寻找匹配的另一个数，需要遍历整个数组，这个效率是 O(n)。而一说到快速定位，立马就能想到 Hash，Hash 的查询效率 O(1)。

我们可以为已迭代过的数（key）用 Hash 存储，同时为了快速获取对应的索引（value），索引（value）也需要得到映射。HashMap 正是为了这个时刻而诞生的...

上面的例子太简单，不太好体现这个实现思路，所以这里就给出一个稍微复杂一点的例子：

Given nums = [2, 7, 11, 15], target = 13,

Because nums[0] + nums[2] = 2 + 11 = 13,
return [0, 2].

每次迭代完一个数，并且该数找不到匹配值，就使用该数以及索引作为键值对，存储到 HashMap 中：

接下来，就是这个 HashMap 该怎么使用的问题了。

除了题目有一定的引导性之外，人的正向思维也导致了我们在看到题目给出的 Example 时，下意识的在数组中组合出两个数的和，然后再去跟 target 进行匹配。

而此刻，HashMap 的使用，则需要我们逆向思考：通过 target 13 减去当前的迭代数 11，再使用差 2去 HashMap 进行搜索。搜索到结果<2, 0>，证明当前迭代数 11跟结果 2匹配。取出结果索引 0，以及当前迭代数的索引 2，构成最终结果返回。时间复杂度 O(n)，空间复杂度 O(n)。

代码

package name.guolanren._1to100._1to10.p1;

import java.util.HashMap;
import java.util.Map;

/**
 * @link https://leetcode.com/problems/two-sum/
 * @author guolanren
 */
public class TwoSum {

    public int[] twoSum(int[] nums, int target) {

        int[] indices = new int[2];
        Map<Integer, Integer> numsMap = new HashMap<>(nums.length);

        for (int i = 0; i < nums.length; i++) {
            int current = nums[i];
            int anotherLookFor =  target - current;
            Integer anotherIndex;

            // 如果待查找的数在 map 中有匹配，则表示找到符合要求的 indices
            if ((anotherIndex = numsMap.get(anotherLookFor)) != null) {
                indices[0] = anotherIndex;
                indices[1] = i;
            }

            numsMap.put(nums[i], i);
        }
        return indices;
    }

}