问题：

两数相加等于目标值

解题思路

1. 容易想到的是双层循环, 时间复杂度O(n^2)。需要关注的是题目提示只有一个答案，并且暗示不该出现自己和自己相加的情形（影响到边界处理条件）。代码如下：

public int[] twoSum(int[] nums, int target) {
        int j = nums.length - 1;
        do {
            int i = 0;
            while (i < j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
                i++;
            }
        } while (--j > 0);
        new IllegalArgumentException("No two sum solution");
    }

Runtime: 20 ms, faster than 41.25% of Java online submissions for Two Sum.
Memory Usage: 38.5 MB, less than 45.94% of Java online submissions for Two Sum.

2. 容易想到的还有先用target与数组里的值做差，再借助Map这种数据结构, 遍历原数组寻找“配对”值下标。时间复杂度变为O(n)

public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> diffMap = new HashMap<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            diffMap.put(target - nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            Integer oriIndex = diffMap.get(nums[i]);
            if (oriIndex != null && i != oriIndex) {
                return new int[]{i, oriIndex};
            }
        }
        return new int[2];
    }

Runtime: 3 ms, faster than 99.77% of Java online submissions for Two Sum.
Memory Usage: 38.3 MB, less than 63.08% of Java online submissions for Two Sum.

3. 看了官方的solution集，发现还有更加紧凑的解法，只需要一次循环。思路是边循环边设置并检查map，如果加和等于target则终止，最坏情况是第一个元素和最后一个元素匹配。

public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }

Runtime: 3 ms, faster than 99.77% of Java online submissions for Two Sum.
Memory Usage: 39.2 MB, less than 21.98% of Java online submissions for Two Sum.

有意思的是，内存使用量比方案2多，会是什么原因呢？