简说Python，号主老表，Python终身学习者，数据分析爱好者，从18年开始分享Python知识，原创文章227篇，写过Python、SQL、Excel入门文章，也写过Web开发、数据分析文章，老表还总结整理了一份2022Python学习资料和电子书资源，关注后私信回复：2022 即可领取。
一、写在前面
- 初衷
想刷leetcode也不是一两天的事情了，之前也有很多人给过建议，于是乎，就给安排上了，一来算法的确是很重要的一块，需要好好学，为了提升自己，再者，这也可以作为微信推文的一块，给大家分享，当然，最重要的是这个过程中会结交到很多志趣相投，有想法的朋友。 - 我们
目前我已经集结了7位研究生学长学姐(各个大学)，一个月内不会加人，大家可以加我微信（zs820553471），进学习交流群讨论，一个月后如果效果不错，很多人感兴趣，我再另建一个专门的算法学习交流群。 - 安排
目前打算一个星期刷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 = 9 test_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 = 0 end_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 = 0 end_time2 = time.time() print("字典遍历耗时："+str(end_time2-start_time2))
- 测试结果：
| 数据量 | 列表耗时 | 字典耗时 |
| 1000 | 0 | 0 |
| 10000 | 0 | 0 |
| 50000 | 0.996ms | 0 |
| 100000 | 1.995ms | 0 |
| 1000000 | 20.944ms | 0 |
| 10000000 | 208.443ms | 0 |
注:0表示的是所花时间极少，我所测的数据可以精确到微秒，极少的意思可表示为少于1微秒。
通过上表很容易看出，列表遍历与字典遍历的天大差别了，不过值得一提的还有，字典生成上要比列表生成慢很多，大家可以自测一下。
