資訊專欄INFORMATION COLUMN
摘要：題目給出一個整型數列表和一個整數，求列表中加起來等于的兩個數，并且這一對是在列表中最先組成對的。因為題目要求是返回最先組對成功的兩個數，所以要找到列表中符合要求的數對中，第二個數最先出現的數對。與擁有類似的結構。
題目：給出一個整型數列表和一個整數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。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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...
閱讀 1583·2021-09-24 10:38
閱讀 1518·2021-09-22 15:15
閱讀 3066·2021-09-09 09:33
閱讀 910·2019-08-30 11:08
閱讀 645·2019-08-30 10:52
閱讀 1258·2019-08-30 10:52
閱讀 2351·2019-08-28 18:01
閱讀 529·2019-08-28 17:55
