原题传送门

1. 题目描述

2. Solution 1: Brute force

1、思路
两层循环穷举所有数，求和，比对target。
2、代码实现

public class Solution1 {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((nums[i] + nums[j]) == target)
                    return new int[]{i, j};
            }
        }
        return null;
    }
}

time complexity: O(n^2)
space coplexity: O(1)
​

3. Solution 2: Hash Table

1、思路
Solution 1使用了两层循环，考虑能否少一层？去掉 内层循环 j?
对于Solution 1: 观察内层循环

for (int j = i + 1; j < n; j++) {
     if ((nums[i] + nums[j]) == target)

做下变形

for (int j = i + 1; j < n; j++) {
    int sub = target - nums[i];
    if (nums[j] == sub){ 

内层循环无非是遍历所有的元素，查找sub，时间复杂度为O(n)。有没有尽可能O(1)的方法查找元素？使用 Hash Table。
​

在Java中，可以把元素存储到 HashMap中，本题中，使用HashMap的目的是在nums中查找sub，若存在返回其下标，故键值对格式为: nums[j] -> j。
​

2、代码实现

/*
    分析:
        破镜重圆法
        1. 遍历nums, 遍历当前元素为nums[i](破镜1), other part(破镜2) = target(圆镜) - nums[i]
        2. 使用HashMap elemIndexMaps保存已遍历过的元素，单个元素结构 nums[i]: i；
        3. 若otherPart in elemIndexMaps，task is done；
        4. 若遍历结束，破镜未能圆，return [-1, -1].
 */

public class Solution2 {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> elemIndexMaps = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int otherPart = target - nums[i];
            if (elemIndexMaps.containsKey(otherPart)) {
                return new int[]{elemIndexMaps.get(otherPart), i};  // Q: 为何要先返回other part的下标？
            }
            elemIndexMaps.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }
}

// A: 因为elemIndexMaps中的元素按照遍历顺序添加，当前遍历元素定晚于otherPart被遍历，即i > index(otherPart)

time complexity: O(n)
space coplexity: O(n)

3. Summary

1、遇到一个问题，在没有任何思路的情况下，总是可以去考虑最朴素、最简单的实现——穷举，然后再考虑穷举的优化。
2、需要Review: Java中 HashMap的基本使用(增删改查)，HashMap源码。