1.两数之和

哈希表

这题我一开始的做法是使用排序+双指针，但是这样需要花费O(nlogn)的时间。使用哈希表就能达到O(n)的时间。

因为本质上遍历数组时，我们需要的是数组里的哪一个数和它的和是某个值，换言之需要的是一个特定的数：target - nums[i]是否在数组中出现过。而又因为和有对称性，我们记录所有出现过的数到哈希表中，在之后遇到匹配的数时就可以以O(1)的时间找到。

哈希表的用处：存储键值对，并且能够以O(1)时间取出键值对，能够判断某个键是否存在。

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        HashMap<Integer, Integer> m = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (m.containsKey(target - nums[i])) {
                return new int[]{i, m.get(target - nums[i])};
            }
            m.put(nums[i], i);
        }
        return null;
    }
}