摘要:题目给出一个整型数列表和一个整数,求列表中加起来等于的两个数,并且这一对是在列表中最先组成对的。因为题目要求是返回最先组对成功的两个数,所以要找到列表中符合要求的数对中,第二个数最先出现的数对。与拥有类似的结构。
题目:给出一个整型数列表和一个整数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 题目链接:https://leetcode.com/problems... 和Count of Smaller Numbers After Self还有count of range su...
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...
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...
摘要:前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写~现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。 顺序整理 1~50 1...
阅读 1448·2021-09-24 10:38
阅读 1437·2021-09-22 15:15
阅读 3028·2021-09-09 09:33
阅读 869·2019-08-30 11:08
阅读 610·2019-08-30 10:52
阅读 1224·2019-08-30 10:52
阅读 2285·2019-08-28 18:01
阅读 488·2019-08-28 17:55