资讯专栏INFORMATION COLUMN

Kata: Sum of Pairs

Drummor / 1999人阅读

摘要:题目给出一个整型数列表和一个整数,求列表中加起来等于的两个数,并且这一对是在列表中最先组成对的。因为题目要求是返回最先组对成功的两个数,所以要找到列表中符合要求的数对中,第二个数最先出现的数对。与拥有类似的结构。

题目:给出一个整型数列表和一个整数sum,求列表中加起来等于sum的两个数,并且这一对是在列表中最先组成对的。

这道题并不难,使用两个for循环很容易做出来。但提交答案时说出了错误:

Process was terminated. It took longer than 12000ms to complete

我在原来答案基础上做了少许更改,可始终达不到要求,无奈只好上网找寻答案。总结后思路如下:

首先出现问题的原因是在处理大列表时,双重for循环耗费太多资源,需要做的是把两个for精减为一个。

因为题目要求是返回最先组对成功的两个数,所以要找到列表中符合要求的数对中,第二个数最先出现的数对。

为了达到上一步骤的目的,把遍历过的数缓存起来,以后遍历的数在缓存好的数中查找是否有配对的,有则返回,无则继续,直到遍历完。

    def sum_pairs(ints, s):
        cache = set()
        for i in ints:
            other = s - i
            if other in cache:
                return [other, i]
            cache.add(i)

修改后的比我那两个for简洁很多,看起来也清楚,时间更是降了很多,所以算法还是很重要的。

另外,缓存之所以用set,而不用list,是因为前者使用hash算法,查找速度为O(1),而后者需要通过下标遍历,查询越长的列表,需要的时间越长。dict与set拥有类似的结构。

所以,如果存储的数据会被反复查询,且量大,那么尽量不用list,而是使用dict或set。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/40936.html

相关文章

  • 493. Reverse Pairs

    摘要:题目链接和还有是一类题,解法都差不多。可以做,但是这道题如果输入是有序的,简单的会超时,所以得用来做。算的方法是比如给的例子,现在分成了左右两部分,拿两个指针和。 493. Reverse Pairs 题目链接:https://leetcode.com/problems... 和Count of Smaller Numbers After Self还有count of range su...

    acrazing 评论0 收藏0
  • 一些做着玩的题

    摘要:这是我在平时有时间的时候做的一些算法上的题目想看更新请移步这里题目描述解法这个问题当时拿到的时候是完全没有思路的,后面上网查询了一下这个题目,知道了使用斐波那契数列就能够解这道题目,,,当然百度作业帮上面也有相应的解法,套路就是题目为一 这是我在平时有时间的时候做的一些算法上的题目 想看更新请移步这里 题目: Climbing Stairs 描述 You are climbing a ...

    cheukyin 评论0 收藏0
  • [LintCode] Amicable Pair

    Problem An amicable pair (m,n) consists of two integers m,n for which the sum of proper divisors (the divisors excluding the number itself) of one number equals the other. Given an integer k, find all...

    mumumu 评论0 收藏0
  • [LeetCode/LintCode] Top K Frequent Words

    LeetCode version Problem Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, t...

    0x584a 评论0 收藏0
  • leetcode 部分解答索引(持续更新~)

    摘要:前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写~现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。 顺序整理 1~50 1...

    leo108 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<