前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Python 版 LeetCode 刷题笔记 #1 两数之和

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

作者头像
TTTEED
发布2020-07-08 19:57:44
8870
发布2020-07-08 19:57:44
举报
文章被收录于专栏:用户6811391的专栏

写在前面

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

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

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

题目

中文题目

第 1 题 两数之和:

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

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

示例:

代码语言:javascript
复制
给定 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:

代码语言:javascript
复制
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

思路

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

代码

代码语言:javascript
复制
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 类的原因:提交格式选择类而不是函数,是为了避免我们提交的函数与评测系统中的函数冲突。封装成类也可以更方便进行时间空间复杂度的评测。

代码语言:javascript
复制
#参考:https://www.zhihu.com/question/31275512/answer/94649438

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

代码语言:javascript
复制
#参考:https://python3-cookbook.readthedocs.io/zh_CN/latest/c07/p03_attach_informatinal_matadata_to_function_arguments.html

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

代码语言:javascript
复制
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 循环遍历的是第二项,我们去其前面来找差值所在。这样会更快的原因是,前者会对后面未知的多项进行差值检测,而后者思路呢则是由已知的少数项来开始差值检测,整体算下来那就是第二种思路会更快一些。我们对代码做下修改来验证:

代码语言:javascript
复制
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 会对列表中的值进行线性扫描,而另外两个(基于哈希表)则可以瞬间完成判断。基于刚才我们的代码,我们选用字典来作进一步优化:

代码语言:javascript
复制
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 !可见,当我们想查找某元素时,利用基于哈希表的字典可能效率会更胜一筹!

结论

第一题,难度在 LeetCode 中是简单程度,但这么琢磨下来,学到的点也不少:算法的设计,数据结构的选择等。

现在做完这个题回头看的话,对于运算方向的设计如果不曾有这个概念大概率是考虑不到的;数据结构的选择也是对字典、列表等非常了解才可能进行优化。说实话,前两天我刚在《利用 Python 进行数据分析》的附录中标记了关于字典基于哈希表的说明,今天还是没能主动运用起字典来,参考了推荐答案才尝试的。

以上,很好的一个开始,明天继续~

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-04-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 TTTEED 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 写在前面
  • 题目
    • 中文题目
      • 英文题目
      • 思路
      • 代码
      • 提交答案
      • 优化
        • 1.调换下两个数的位置
          • 2.更换数据结构
          • 结论
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档