题目描述

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

原文地址

思路方法

最先能想到方法就是数组中每个元素依次和后面的元素相加判断是否符合要求，但是这种方法时间复杂度太高了 O(n^2)。

为了降低时间复杂度，则采取扫描一遍的方式：
1.把已经扫描过的数组按照{数值：索引}存放在字典 dic 里面；
2.扫描到当前的数组值，查看字典是否存在满足题目的值；

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
         """
        #dic 存放已经扫描过的{数组值 : 该数组下标}
        dic = {}
        #从头遍历数组
        for i in range(len(nums)):
            if target - nums[i] in dic:
                #如果当前数组值和字典中存在的值满足特定target，则返回当前数组织和字典中的索引
                return [dic[target - nums[i]], i]
            dic[nums[i]] = i

知识点

1.Python 内置字典：dictionary 简称 dict，在其它语言中也称为 map，使用键 - 值（key-value）存储，具有极快的查找速度。如：

>>>dic = {‘Michael’: 95, 'Bob': 75, 'Tracy', 85}
>>>dic['Bob'] 
75