1. Two Sum

Leetcode Array Hash Table

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].

分析

使用哈希表，当遍历数组的时候，把数组元素的互补target - nums[i]和当前下标(i)插入到哈希表中，当数组元素已经存在于哈希表中时，说明找到了答案，返回哈希表值和当前下标。

Java

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

Python

def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    result = {}
    index = 0;
    for i in nums:
        if i in result:
            return [index, result[i]]
        else:
            result[target-i] = index
        index += 1;