資訊專欄INFORMATION COLUMN
摘要：題目給出一個整型數(shù)列表和一個整數(shù)，求列表中加起來等于的兩個數(shù)，并且這一對是在列表中最先組成對的。因為題目要求是返回最先組對成功的兩個數(shù)，所以要找到列表中符合要求的數(shù)對中，第二個數(shù)最先出現(xiàn)的數(shù)對。與擁有類似的結(jié)構(gòu)。
題目：給出一個整型數(shù)列表和一個整數(shù)sum，求列表中加起來等于sum的兩個數(shù)，并且這一對是在列表中最先組成對的。
這道題并不難，使用兩個for循環(huán)很容易做出來。但提交答案時說出了錯誤：
Process was terminated. It took longer than 12000ms to complete
我在原來答案基礎(chǔ)上做了少許更改，可始終達不到要求，無奈只好上網(wǎng)找尋答案?？偨Y(jié)后思路如下：
首先出現(xiàn)問題的原因是在處理大列表時，雙重for循環(huán)耗費太多資源，需要做的是把兩個for精減為一個。
因為題目要求是返回最先組對成功的兩個數(shù)，所以要找到列表中符合要求的數(shù)對中，第二個數(shù)最先出現(xiàn)的數(shù)對。
為了達到上一步驟的目的，把遍歷過的數(shù)緩存起來，以后遍歷的數(shù)在緩存好的數(shù)中查找是否有配對的，有則返回，無則繼續(xù)，直到遍歷完。
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)，而后者需要通過下標(biāo)遍歷，查詢越長的列表，需要的時間越長。dict與set擁有類似的結(jié)構(gòu)。
所以，如果存儲的數(shù)據(jù)會被反復(fù)查詢，且量大，那么盡量不用list，而是使用dict或set。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/40936.html
摘要：題目鏈接和還有是一類題，解法都差不多?？梢宰觯沁@道題如果輸入是有序的，簡單的會超時，所以得用來做。算的方法是比如給的例子，現(xiàn)在分成了左右兩部分，拿兩個指針和。 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...
摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個索引嘻嘻。 順序整理 1~50 1...
閱讀 1588·2021-09-24 10:38
閱讀 1524·2021-09-22 15:15
閱讀 3074·2021-09-09 09:33
閱讀 913·2019-08-30 11:08
閱讀 650·2019-08-30 10:52
閱讀 1263·2019-08-30 10:52
閱讀 2358·2019-08-28 18:01
閱讀 533·2019-08-28 17:55
