Python 版 LeetCode 刷题笔记 #1 两数之和

TTTEED

发布于 2020-07-08 19:57:44

8870

发布于 2020-07-08 19:57:44

写在前面

学 Python 也有一段时间了，一直维持在入门阶段，最近想集中精力精进下编码能力，所以把刷题当作一个练习，也看看自己能坚持几道题。

此外，虽然也写过些简单的代码，初次接触 LeetCode 还是有点懵逼的，尤其是提交答案区域格式是个 class Solution，而且其函数定义方法与平时用到的也有些区别，瞬间自我怀疑难道函数定义自己记错了？见得多、理解了就还挺有收获的。

刷题过程呢，针对每道题目，我打算记录下自己的思路和解答过程。再根据提交答案的比对，拆解参考答案或者其它优质答案来进行自我的优化，最终给出一个最推荐的解答。也希望这个记录过程不再仅仅是一个解题，能多一些分析的记录吧。

题目

中文题目

第 1 题两数之和：

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum

英文题目

Question 1 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].

思路

nums 是列表，对其进行遍历在所难免，通过 for 循环遍历，既然两数之和可以拿到，可以用和减去我们遍历的项，看这个差是否在列表的剩余项中，如果在，输出满足条件的两项索引。

代码

for i,item in enumerate(nums):
    # 截取剩余部分的列表，避免检查重复
    temp = nums[i+1:]
    # 差值
    second = target-item 
    # 如果差值在剩余项，输出两项的索引
    if second in temp:
        return [i,temp.index(second)+i+1]

提交答案

提交区域可以看到，有个 class Solution，定义的函数 twoSum(参数) -> 结果这个形式也比较奇怪。一番搜索，解惑如下。

封装成 class 类的原因：提交格式选择类而不是函数，是为了避免我们提交的函数与评测系统中的函数冲突。封装成类也可以更方便进行时间空间复杂度的评测。

#参考：https://www.zhihu.com/question/31275512/answer/94649438

提交区中的函数定义除了正常的参数，还夹杂了数据类型以及箭头指向等？这其实是为 python 函数参数的元信息，用于提示该函数输入参数和返回值的数据类型。

#参考：https://python3-cookbook.readthedocs.io/zh_CN/latest/c07/p03_attach_informatinal_matadata_to_function_arguments.html

搞懂这个，我们把刚自己写好的函数迁移到答案中、对应好要提交的函数参数名称即可：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i,item in enumerate(nums):
            temp = nums[i+1:]
            second = target-item 
            if second in temp:
                return [i,temp.index(second)+i+1]

提交后，我们可以得到自己代码运行的测评结果：

中文区结果：

执行用时 : 864 ms, 在所有 Python3 提交中击败了37.48% 的用户内存消耗 : 14.3 MB, 在所有 Python3 提交中击败了26.60% 的用户

英文版结果：

Runtime: 1108 ms, faster than 28.08% of Python3 online submissions for Two Sum. Memory Usage: 14.6 MB, less than 20.00% of Python3 online submissions for Two Sum.

因为中文区代码提交量相较原英文社区少些，故数据会略有差异。

优化

结果现实我们只优于提交代码的 2-3 成，并不算好，我们来继续优化。

1.调换下两个数的位置

这算挺神奇一发现，刚我们在 for 循环中，针对得到的第 i 项 item，检测差值是否在 nums[i+1:] 中，也就是在该项后面寻找差值。换一种思路，我们现在 for 循环遍历的是第二项，我们去其前面来找差值所在。这样会更快的原因是，前者会对后面未知的多项进行差值检测，而后者思路呢则是由已知的少数项来开始差值检测，整体算下来那就是第二种思路会更快一些。我们对代码做下修改来验证：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:        
        for i,item in enumerate(nums):
            # 选择 i 之前的列表片段
            temp = nums[:i]
            second = target-item 
            if second in temp:
                return [temp.index(second),i]

表现结果：

Runtime: 540 ms, faster than 31.47% of Python3 online submissions for Two Sum. Memory Usage: 14.6 MB, less than 18.14% of Python3 online submissions for Two Sum.

不看比例，运行时间从 1108 ms 降到了 540 ms ！惊了个呆，思路基本一致，只不过调整了下方向。。

2.更换数据结构

判断列表是否含有某个值的操作比字典（dict）和集合（set）慢得多，因为 Python 会对列表中的值进行线性扫描，而另外两个（基于哈希表）则可以瞬间完成判断。基于刚才我们的代码，我们选用字典来作进一步优化：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]: 
        source={}
        for i,item in enumerate(nums):
            second = target-item 
            if source.get(second) is not None:
                return [source.get(second),i]
            source[item]=i

表现结果：

Runtime: 48 ms, faster than 77.68% of Python3 online submissions for Two Sum. Memory Usage: 15.3 MB, less than 5.11% of Python3 online submissions for Two Sum.

我们可以看到，运行时间从 540ms 降到了 48ms ！可见，当我们想查找某元素时，利用基于哈希表的字典可能效率会更胜一筹！