1.Two Sum——Python实现

Description：
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值。
        假设每个输入只有一组解，并且不能够两次使用同一个位置上的数。

• 最好想的方法：用两次for循环，时间复杂度为O（n^2）

• 改进方法：使用哈希表。代码如下：

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dict= {}
        for i in range(0,len(nums)):
            if nums[i] in dict :
                return dict[nums[i]] ,i
            else :
                dict[target - nums[i]] = i

时间复杂度为O（n）