1. Two Sum

第一题，经典的空间换时间。这个解法太简单了，知道了就不难，但要凭空想出来还是需要点直觉的。后续还有有衍生版的3 Sum、4 Sum之类的。

思考过程有点类似逆转裁判的感觉。。。不要去想“哪些数加起来是结果”，而是想“当前数加上什么才是结果”。

这道题经常被我用来检测面试者是否刷过leetcode。。。

UPDATE：leetcode的题目好像更新了，返回结果中的下标不需要+1了，我就不改代码了

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        // key是要找的数，value是数组下标
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

        for (int i = 0; i < nums.length; i++) {
            int value = nums[i];
            if (map.containsKey(value)) {
                // 如果找到了要找的数字，就返回结果
                return new int[] {map.get(value) + 1, i + 1};
            } else {
                // 对下标i而言，要找的数字是target-value
                map.put(target - value, i);
            }
        }

        return null;
    }
}