Kata: Sum of Pairs

Drummor 發(fā)布于2019-07-30 14:48 / 2025人閱讀

摘要：題目給出一個(gè)整型數(shù)列表和一個(gè)整數(shù)，求列表中加起來(lái)等于的兩個(gè)數(shù)，并且這一對(duì)是在列表中最先組成對(duì)的。因?yàn)轭}目要求是返回最先組對(duì)成功的兩個(gè)數(shù)，所以要找到列表中符合要求的數(shù)對(duì)中，第二個(gè)數(shù)最先出現(xiàn)的數(shù)對(duì)。與擁有類(lèi)似的結(jié)構(gòu)。

題目：給出一個(gè)整型數(shù)列表和一個(gè)整數(shù)sum，求列表中加起來(lái)等于sum的兩個(gè)數(shù)，并且這一對(duì)是在列表中最先組成對(duì)的。

這道題并不難，使用兩個(gè)for循環(huán)很容易做出來(lái)。但提交答案時(shí)說(shuō)出了錯(cuò)誤：

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

我在原來(lái)答案基礎(chǔ)上做了少許更改，可始終達(dá)不到要求，無(wú)奈只好上網(wǎng)找尋答案。總結(jié)后思路如下：

首先出現(xiàn)問(wèn)題的原因是在處理大列表時(shí)，雙重for循環(huán)耗費(fèi)太多資源，需要做的是把兩個(gè)for精減為一個(gè)。

因?yàn)轭}目要求是返回最先組對(duì)成功的兩個(gè)數(shù)，所以要找到列表中符合要求的數(shù)對(duì)中，第二個(gè)數(shù)最先出現(xiàn)的數(shù)對(duì)。

為了達(dá)到上一步驟的目的，把遍歷過(guò)的數(shù)緩存起來(lái)，以后遍歷的數(shù)在緩存好的數(shù)中查找是否有配對(duì)的，有則返回，無(wú)則繼續(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)

修改后的比我那兩個(gè)for簡(jiǎn)潔很多，看起來(lái)也清楚，時(shí)間更是降了很多，所以算法還是很重要的。

另外，緩存之所以用set，而不用list，是因?yàn)榍罢呤褂胔ash算法，查找速度為O(1)，而后者需要通過(guò)下標(biāo)遍歷，查詢(xún)?cè)介L(zhǎng)的列表，需要的時(shí)間越長(zhǎng)。dict與set擁有類(lèi)似的結(jié)構(gòu)。

所以，如果存儲(chǔ)的數(shù)據(jù)會(huì)被反復(fù)查詢(xún)，且量大，那么盡量不用list，而是使用dict或set。