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

叁歲伎倆 2022-04-16 05:23 135阅读 0赞

题干：

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，题一解答完毕。