[python解法] LEETCODE 算法题一：two sum

53 阅读 0 评论 35 点赞

我是靠谱客的博主听话绿茶，最近开发中收集的这篇文章主要介绍[python解法] LEETCODE 算法题一：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.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

总结一下我解这道题的几种思路，并附上耗时和分析

注：由于 leetcode 上不同时期得到的耗时有比较大的差别，我的操作时间是2018.11.11左右。

解法一：

class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
array_len = len(nums)
for i in range(0, array_len-1):
for j in range(i+1, array_len):
if (nums[i] + nums[j] == target):
print "%d, %d" %(i,j)
return (i,j)

耗时：3472ms

最简单的方法，两级循环，暴力破解，通过检查相加结果是否等于target来判定

解法二：

class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i in range(len(nums)):
tar_num = target - nums[i]
for j in range(i+1, len(nums)):
if nums[j] == tar_num:
return [i,j]

耗时：2832ms

通过减少加法运算的次数，达到提高速度的目的

跟方法一相比，执行加法的次数大幅减少，只在外层循环中执行一次减法，在二级循环中只比较是否相等

解法三：

class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
length = len(nums)
for i, num in enumerate(nums):
tar_num = target - num
for j in range(i+1, length):
if nums[j] == tar_num:
return [i,j]

耗时：2472ms

通过减少寻址的方式，加快程序运行速度。

将len(nums) 的结果放在一个变量中，而不是在每次进入循环的时候去进行运算。由于每进入一次二级循环，都要执行一次len(nums) 运算，所以修改之后会对性能有提升。

同时，将一级循环中的for i in range(len(nums)): 修改为for i, num in enumerate(nums):

这样做的目的是避免每次做减法运算的时候，都进行一次取址操作。将运算对象提前准备好，而不是要用到的时候再去取。

> 注：enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标

解法四：

class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i, num in enumerate(nums):
tar_num = target - num
if (tar_num in nums):
if (i != nums.index(tar_num)):
return [i, nums.index(tar_num)]

耗时：960ms

方法三已经达到了二级循环的性能极限（笔者想不到还能怎么优化了）。如果要增加程序执行速度，必须采用一级循环的方式。

将减下来的差值，直接在整个输入数组中寻找。如果能找到，且对应的下标不等于本身（即所求的target不等于该数的两倍），则返回结果

这种方法，将原先第二级循环的工作量交给了默认方法“in”来解决，加快了运行速度

解法五：

class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
tar_arr = []
for i, num in enumerate(nums):
tar_num = target - num
try:
j = tar_arr.index(num)
return [j,i]
except ValueError:
tar_arr.append(tar_num)

耗时：176ms

在上一种方式上的改进。既然是通过在数组中查找tar_num，不如新建一个数组，在每次查找失败的时候，添加到新数组中，这样可以省去查找的很多时间。如果用index方法找不到变量，python会报ValueError，捕获这个error并append数组即可

解法六：

class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
dicty = {}
for i, num in enumerate(nums):
tar_num = target - num
if tar_num not in dicty:
dicty[num] = i
else:
return [dicty[tar_num], i]

耗时：28ms

用字典代替列表，速度会得到进一步提升。

字典相对于列表的优势在于：查找和插入的速度极快，不会随着key的增加而变慢；

字典相对于列表的劣势在于：需要占用大量的内存，内存浪费多

在本题中使用字典作为查找和插入媒介，可以极大地提升运行速度

解法六+：

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

耗时：20ms

在方法六基础上稍作修改，将else和if的判断顺序做了掉换。确认tar_num是否在当前字典中，比确认不在要快。确认不在，需要花更多时间才能得到结论。所以该方法可以得到更快的速度

综上，运行速度从最起始的3472ms，加快到20ms，题一解答完毕。