1. Two Sum

Easy Array Hash Table

Description

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

Solution

方案1

下意识的解决方案，遍历数组中每一个元素 x，并寻找数组中是否存在 target-x 。

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

• 时间复杂度：O(n^2)，对于每一个元素，都会对数组中剩余部分进行遍历以寻找 target-x ，显然，时间复杂度为 O(n^2)
• 空间复杂度：O(1)

方案2

查找元素，我们很自然的会想到哈希表，哈希表的查找时间几乎恒定为 O(1)。在哈希表中以索引为值，索引处的值为键进行存储，只需要一次遍历，对于每一个元素 x，判断哈希表中是否 containsKey(target-x)，不存在则将该元素塞入哈希表，若存在直接返回该元素和对应的 target-x。

public int[] solution2(int[] nums, int target) {

    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (map.containsKey(target - nums[i]))
            return new int[]{i, map.get(target - nums[i])};
        map.put(nums[i], i);
    }
    return null;
}

• 时间复杂度：O(n)，只需一次遍历，且查找时间为 O(1)
• 空间复杂度：O(n)，需要的额外空间为一个哈希表，至多存储 n 个元素

方案2 就是典型的空间换时间，在对空间限制不大的情况下，将大大提升算法的效率。