【记录帖】(No.001)从零打卡刷Leetcode

写在前边:

小詹一直觉得自己编程能力不强,想在网上刷题,又怕不能坚持。不知道有木有和小伙伴和小詹一样想找个人一起刷题呢?欢迎和小詹一起定期刷leetcode,每周一周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!欢迎小伙伴们把自己的思路在留言区分享出来噢~


No.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.

题目大意:给出一个数字列表和一个目标值(target),假设列表中有且仅有两个数相加等于目标值,我们要做的就是找到这两个数,并返回他们的索引值。

例如:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].


小詹第一反应就是两层循环就可以解决,小case,的确思路简单,但是时间复杂度,你懂得!很简单就能想到的代码如下:

def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    result = []
    for i in range(len(nums)):
       for j in range(i+1, len(nums)):
           if nums[i] + nums[j] == target:
               result.append(i)
               result.append(j)
               return result

其实这里也可以用一层循环即可实现,因为我们知道有且仅有一个解;我们可以通过判断target与某一个元素的差值是否也在列表之中即可,这个和两层循环思路类似,但是不难想到计算次数就下降了,代码如下:

def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    result = []
    for i in range(len(nums)):
       oneNum = nums[i]
       twoNum  = target - oneNum
       if twoNum in nums:
          j = nums.index(twoNum)
          if i != j:
             result.append(i)
             result.append(j)
             return result

的确两种方案都轻松通过了,but用时过长,排名老靠后了。之后小詹在网上找到了另一种方案,整体思路和一层循环的方案二有点类似:通过创建字典,将nums里的值和序号对应起来,并创建另一个字典存储目标值(Target)-nums的值,通过判断该值是否在nums内进行判断并返回其对应索引值,代码如下:

def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 创建字典一,存储输入列表的元素值和对应索引
        num_dict = {nums[i]:i for i in range(len(nums))}
        print(num_dict)
        # 创建另一个字典,存储target-列表中的元素的值,小詹称为num_r吧,好表达
        num_dict2 = {i:target-nums[i] for i in range(len(nums))}
        print(num_dict2)
        # 判断num_r是否是输入列表中的元素,如果是返回索引值,不是则往下进行
        result = []
        for i in range(len(nums)):
            j = num_dict.get(num_dict2.get(i))
            if (j is not None) and (j!=i):
                result = [i,j]
                break
        return result

该方案,在时间效率上还较为理想,小詹亲测结果排名如下:

不知道小伙伴们能否提出更加节约时间的方案呢?如果有请联系小詹,在下一次打卡时候分享给大家!独乐乐不如众乐乐噢!

往期推荐

休息是为了走更远的路

Python系列之——在北京当房奴的日子~

反爬虫和反反爬虫(下篇)

本文分享自微信公众号 - 小詹学Python(xiaoxiaozhantongxue)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-05-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI科技大本营的专栏

送书 | 跟我一起学《流畅的Python》

本文引自图灵新书《流畅的Python》的第一章——Python数据模型。本书由奋战在Python开发一线近20年的Luciano Ramalho执笔,Victo...

43540
来自专栏PPV课数据科学社区

零基础到精通Python,从这篇文章开始

关键词:Python,入门 正文: 本文由rever4433, Tocy, Tony, 南宫冰郁, 透过树叶的光等协作翻译,发表于开源中国。 什么是 Pytho...

31760
来自专栏owent

不知道是哪一年的腾讯马拉松题目 照片评级 解题报告

结果就一不小心看到了这个充满回忆的ACM模式竞赛,还有咱腾讯的,就忍不住看了一下。

7410
来自专栏take time, save time

你所能用到的数据结构(八)

十一、不能被应用的理论不是好研究 前面介绍了堆栈的一些小小的理论模型,那么这样一个东西有什么作用呢?实际中不可能有那么一辆停在站台前方堵死的火车的,即使有,也...

28640
来自专栏好好学java的技术栈

“365算法每日学计划”:java语言基础题目及解答(01-05打卡)

如果有小伙伴很少接触到这种题目的话,可能会觉得有点陌生,不知道从何下手,可能一开始我们能想到“最笨”的方法,但是也觉得挺有“娱乐性”的方法。

16950
来自专栏前端布道

JavaScript 浮点数陷阱及解法

众所周知,JavaScript 浮点数运算时经常遇到会 0.000000001 和 0.999999999 这样奇怪的结果,如 0.1+0.2=0.300000...

43830
来自专栏进击的程序猿

进击算法:字符串匹配的 BM 算法

各种文本编辑器的 "查找" 功能(Ctrl+F),大多采用 Boyer-Moore 算法。

36230
来自专栏小樱的经验随笔

BZOJ 3670: [Noi2014]动物园【KMP变形 】

3670: [Noi2014]动物园 Time Limit: 10 Sec  Memory Limit: 512 MB Submit: 2738  Solve...

37170
来自专栏zaking's

js算法初窥03(搜索及去重算法)

14520
来自专栏从流域到海域

《笨办法学Python》 第35课手记

《笨办法学Python》 第35课手记 本节课讲函数和分支的,实际上是一次综合练习,代码有点长,请先纠正代码中的错误使脚本能够运行。 原代码中使用三个空格来进行...

232100

扫码关注云+社区

领取腾讯云代金券