Two Sum

问题描述

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.

示例

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

算法思路

比较容易想到的是，用两个循环，两两元素之和与目标数比较，但是算法复杂度为O（n^2）,会超时。另一种办法是用字典和枚举，用字典存储查询过的值和索引，用枚举来遍历整个列表，算法复杂度为O（n）,所以推荐用第二种方法。

代码实现（python3）

方法一：

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        r = []
        l = len(nums)
        for i in range(l):
            for j in range(l):
                if nums[i] + nums[j] == target and i != j:
                    return i,j
        r = r.append(i,j)
        return r

方法二：

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        collected = {}
        for i,x in enumerate(nums):
            diff = target-x
            if diff in collected:
                return [collected[diff], i]
            collected[x] = i

参考资料

1. https://www.tutorialspoint.com/python/python_dictionary.htm Python - Dictionary
2. https://www.geeksforgeeks.org/enumerate-in-python/ Enumerate() in Python
3. https://leetcode.com/problems/two-sum/ two-sum