2 Sum

Question

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are NOT zero-based.

Example numbers=[2, 7, 11, 15], target=9

return [1, 2]

Note You may assume that each input would have exactly one solution

Challenge Either of the following solutions are acceptable:

• O(n) Space, O(nlogn) Time
• O(n) Space, O(n) Time

Thoughts

问题分析

• array不是sorted
• array的长度不一定大于2

Hashmap

两个数的sum Xi + Xj = target 可以变为找Xj = target - Xi

允许O（n）的space,可以先用hashmap遍历一遍，存在hashmap里 再遍历各个元素，找target - Xi

Sort后2个pointer方法

Solution

class Solution:
    """
    @param numbers : An array of Integer
    @param target : target = numbers[index1] + numbers[index2]
    @return : [index1 + 1, index2 + 1] (index1 < index2)
    """
    def twoSum(self, numbers, target):
        # write your code here
        in len(numbers) < 2:
            return None
        dic = {}
        for idx, num in enumerate(numbers):
            dic[num] = idx
        for idx, num in enumerate(numbers):
            t = target - num
            if t in dic:
                index1 = idx
                index2 = dic[t]

        if index1 < index2:
            return [index1+1, index2+1]
        else:
            return [index2+1, index1+1]