两数之和

写个题解。
原思路：

1. 首先想到能不能排序。若是有序数组，将会节省不小的时间开销（target/2往后的不用看；每轮一旦两数和大于 target 即可 break）。
2. 再看题目要求输出 index，若先排序 index 就乱了，貌似没戏。
3. 还不死心，想能不能通过 Map 来存取改动前的 index。
4. 取一种折中的办法，数组不用完全有序，只要设立一个 target/2 基准点即可（类似快排），因为两数不可能同时出现在 target/2 的同一侧！（貌似能成）
5. map存取所有移动过元素的原索引，以及所有左侧元素索引，这样只需遍历右侧的元素，看target与元素之差存在 map 中的值（索引）即可。
6. 照着这个思路写完了，部分用例未通过（如[0,2,3,0],0，也就是 target 恰好等于最小值的情况）
7. 抓耳挠腮过程中偷瞄了一眼 LeetCode 上的题解，泪流满面。相比之下我这都什么废物思路。直接给跪了，怒删代码。
   

LeetCode 题解思路：遍历，每次判断 target - current 是否在 Map 中，若在直接返回；若不在将 current 和对应索引存入 Map。
注意：因为每次找的是 target 和当前元素的差值，因此理论上不存在元素覆盖的问题（因为题目声明只有唯一解）。

下面贴个代码，真·信达雅。

public int[] twoSum (int[] numbers, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int cur = 0, tmp; cur < numbers.length; cur++){
        tmp = numbers[cur];
        if (map.containsKey(target - tmp)){
            return new int[] {map.get(target - tmp) + 1, cur + 1};
        }
        map.put(tmp, cur);
    }
    throw new RuntimeException("results not exits");
}