56. Two Sum

题目

https://www.lintcode.com/problem/two-sum/description?_from=ladder&&fromId=2

实现

1. 定义 hash 表用于存放 number: index
2. 遍历数组，判断 target - number 的值是否存在于 hash 表里，如果存在，那么返回 hash[target - number] 和当前索引 i

代码

class Solution:
    """
    @param numbers: An array of Integer
    @param target: target = numbers[index1] + numbers[index2]
    @return: [index1, index2] (index1 < index2)
    """

    def twoSum(self, numbers, target):
        if numbers is None:
            return [-1, -1]

        number_hash = {}

        for i, number in enumerate(numbers):
            offset = target - number
            if offset in number_hash:
                return [number_hash[offset], i]

            number_hash[number] = i

        return [-1, -1]