LeetCode 第一题

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

使用python 解法 ：

暴力解法：

class Solution(object):
    def twoSum(self, nums, target):
        result = []
        t1 = time.time()
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    result.append(i)
                    result.append(j)
                    print(time.time() - t1)
                    return result

数值比较少的时候没有问题，当数值过多的时候，会出现超时

字典解法：

class Solution(object):
    def twoSum(self, nums, target):
        size = 0
        d = {}
        while size < len(nums):
            #先把数组存到字典里面
            if not nums[size] in d:#key不在字典里，进行赋值
                d[nums[size]] = size
            if target - nums[size] in d:# nums[size] 和 target - nums[size]都在字典里，即存在和为他人个体/的两个数
                # 这里key 有可能指向同一个数（即 target - nums[size] =  nums[size]时，他其实只有一个数）
                if d[target - nums[size]] < d[nums[size]]:
                    # d的值从小到大输出
                    result = [d[target - nums[size]], d[nums[size]]]
                    return resul
# 注意size = size + 1是和最外层的if平级的
            size = size + 1

这种解法是保证数组没有相同的数值，如果有相同的数值就会输出错误，不过解法的思想是正确的。

第二种字典解法：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
   
        dic = dict()
        for index,value in enumerate(nums):
            sub = target - value
            if sub in dic:
                return [dic[sub],index]
            else:
                dic[value] = index

其实是用了enmumerate ( ) 方法

Python enumerate() 函数

描述

enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。
Python 2.3. 以上版本可用，2.6 添加 start 参数。

语法

以下是 enumerate() 方法的语法:

enumerate(sequence, [start=0])

参数

sequence -- 一个序列、迭代器或其他支持迭代对象。

start -- 下标起始位置。

返回值

返回 enumerate(枚举) 对象。

实例

以下展示了使用 enumerate() 方法的实例：

>>>seasons = ['Spring', 'Summer', 'Fall', 'Winter']>>> list(enumerate(seasons))[(0, 'Spring'), (1, 'Summer'), (2, 'Fall'), (3, 'Winter')]>>> list(enumerate(seasons, start=1)) # 下标从 1 开始[(1, 'Spring'), (2, 'Summer'), (3, 'Fall'), (4, 'Winter')]

普通的 for 循环

>>>i = 0>>> seq = ['one', 'two', 'three']>>> for element in seq: ... print i, seq[i]... i +=1... 0 one1 two2 three

for 循环使用 enumerate

>>>seq = ['one', 'two', 'three']>>> for i, element in enumerate(seq): ... print i, element... 0 one1 two2 three