听说你还在写双层 for 循环解两数之和？

作者：老表

2021 年 11 月 13 日
本文字数：3004 字
阅读完需：约 10 分钟

这是我参与 11 月更文挑战的第 5 天。

一、写在前面

大家好，我是爱猫爱技术的老表。

初衷想刷 leetcode 也不是一两天的事情了，之前也有很多人给过建议，于是乎，就给安排上了，一来算法的确是很重要的一块，需要好好学，为了提升自己，再者，这也可以作为掘金分享的一块，给大家分享，当然，最重要的是这个过程中会结交到很多志趣相投，有想法的朋友。

安排目前打算一个星期刷 2-3 个题，推文分享进度可能会慢一点，但一个星期至少也会有两篇，期待大家参与。

二、今日题目

题干:

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]

复制代码

三、分析

这个题目看似很简单，在一个列表(nums)里面找到两数,满足和为事先指定好的数(target)即可,其实有陷阱，第一：很多人一看到题目自然想到两层 for 循环解决问题，but这种人人都想到的问题你若是也这么做，如果你就这种程度，面试失败也不算亏；第二：这题的返回值到底是什么？你看清了吗？它的返回值是一个列表，列表里是int型的数据，这个数据并不是我们找到的满足算式的数，而是这个数在列表里对应的下标,你中招了吗？第三：双 for 循环极易出错的地方，不能出现自己加自己的情况。

四、解题

方法一：又蠢又笨的双重 for 循环

class Solution(object):    def twoSum(self, nums, target):        """        :type nums: List[int]        :type target: int        :rtype: List[int]        """        l = len(nums)        for a in range(l):            for b in range(l):                if a != b:                    if nums[a]+nums[b] == target:                        return [a,b]nums = [2, 7, 11, 15]target = 9test_o = Solution()result = test_o.twoSum(nums,target)print(result)

复制代码

提交结果：

方法一运行结果

测试数据：29 组运行时间：7000ms 击败人百分比:3.72%

方法二：比双 for 聪明一点

我们作图分析易发现，其实直接双重 for 循环进行运算是有一半的运算是没有意义的，比如a+b和b+a其实是一模一样的，如下图分析：

小聪明

如何把重复的去掉减少计算机运行量来提升运行速度呢？

我想的比较简单，利用标识位，建立一个和给定整数列表一样长的数组，初始值为全为 0，第一层 for 循环运行一次，该位对应的标识值由 0 变成 1，在第二层 for 运算时先判断对应的数据位上的标识符是否都为 0，为 0 则进行运算比较，否则说明互相之间已经运算过，就continue,代码如下：

class Solution(object):    def twoSum(self, nums, target):        """        :type nums: List[int]        :type target: int        :rtype: List[int]        """        flags = [0, 0, 0, 0]        l = len(nums)        for a in range(l):            flags[a]=1            for b in range(l):                if flags[b]==0:                    if nums[a]+nums[b] == target:                        return [a,b]        # 另一种简单方法                     # l = len(nums)        # for a in range(l):        #    for b in range(a+1,l):        #       if nums[a] + nums[b] == target:        #            return [a, b]

复制代码

提交结果：

方法二运行结果

测试数据：29 组运行时间：6784ms 击败人百分比:5.06%

方法三：一层循环（偷瞄了小詹学长的方法）

class Solution(object):    def twoSum(self, nums, target):        """        :type nums: List[int]        :type target: int        :rtype: List[int]        """       #flags = [0 for i in range(len(nums))]        l = len(nums)        for a in range(l):            one_unm = nums[a]            other_one = target - one_unm            if other_one in nums:                b = nums.index(other_one)                if a != b:                    if a>b:                        return [b,a]                    return [a,b]

复制代码

提交结果：

方法三运行结果

测试数据：29 组运行时间：892ms 击败人百分比:64.16%

方法四：一层 for 循环优化（小詹读者【村前河水流】提供）

class Solution(object):    def twoSum(self, nums, target):        """        :type nums: List[int]        :type target: int        :rtype: List[int]        """       #flags = [0 for i in range(len(nums))]        l = len(nums)        dict_nums = {nums[i]:i for i in range(l)}        for a in range(l):            one_unm = nums[a]            other_one = target - one_unm            if other_one in dict_nums and a!= dict_nums[other_one]:                return [a,dict_nums[other_one]]

复制代码

提交结果：

方法四运行结果

测试数据：29 组运行时间：28ms 击败人百分比:98.76%

五、疑惑

方法一和二，由双重 for 循环，时间复杂度高，耗时长没话说，可方法三和方法四的差别，怎么也这么大呢？

我仔细研究了一下，方法三和四最大的差别就是：前者是列表遍历查找，后者是字典遍历查找，那么关键点来了，到底是不是这个问题呢？

列表与字典遍历性能测试代码：

import time
list_01 = [str(i) for i in range(1000)]start_time = time.time()if 'a' in list_01 :    a = 0end_time = time.time()print("列表遍历耗时："+str(end_time-start_time))
dict_01 = {str(i):i for i in range(1000)}start_time2 = time.time()if 'a' in dict_01 :    a = 0end_time2 = time.time()print("字典遍历耗时："+str(end_time2-start_time2))

复制代码

测试结果：

注:0 表示的是所花时间极少，我所测的数据可以精确到微秒，极少的意思可表示为少于 1 微秒。

通过上表很容易看出，列表遍历与字典遍历的天大差别了，不过值得一提的还有，字典生成上要比列表生成慢很多，大家可以自测一下。

六、结语

啥也不说，刷题就是要坚持。

思想很复杂，

实现很有趣，

只要不放弃，

终有成名日。

—《老表打油诗》

下期见，我是爱猫爱技术的老表，如果觉得本文对你学习有所帮助，欢迎点赞、评论、关注我！

发布于: 5 小时前阅读数: 9

原文链接:【http://xie.infoq.cn/article/1cfe844ed8cbb645c7df3a2cf】。文章转载请联系作者。

老表

关注

公众号｜简说Python 2018.09.23 加入

【公众号：简说Python】爱猫爱技术，Python终身学习者、数据分析爱好者、Go语言内卷机。

发布

暂无评论

创作场景

听说你还在写双层 for 循环解两数之和？

一、写在前面

二、今日题目

三、 分析

四、解题

五、疑惑

六、结语

老表

评论

三、分析