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;
}

方案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;
}

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

Table of Contents