文/良宵聽雨。授權(quán)“游戲夜讀”發(fā)表。
打開LeetCode找到一個小游戲
\1. Two Sum
Easy
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
自助使用Python3款答題紙
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
開始答題……其他略。題目中有兩個假設(shè)：
1 有且僅有一個解；
2 同一個元素不能被使用兩次。
嘗試的5種方法阅懦，失敗了4次
# 方法1：循環(huán)遍歷列表中的數(shù)，一個一個找
# for i in nums:
# for j in nums:
# if nums.index(i) != nums.index(j):
# if (i+j)==target:
# return [nums.index(i), nums.index(j)]
# 上述方法1有個漏洞：當i=j徘铝，比如遇到[3,3]耳胎，.index()的判斷就不好用了
# 方法2：基于方法1惯吕，循環(huán)遍歷列表的索引，這樣就避免數(shù)值相同的bug啦
# for i in range(len(nums)):
# for j in range(len(nums)):
# if i != j:
# if nums[i] + nums[j] == target:
# return [i, j]
# 上述方法2雖然可行怕午，但是Time Limit Exceeded废登，說明效率太低，被淘汰了
# 方法3：根據(jù)題目中說的假設(shè)（恰有一個答案）郁惜，直接匹配差值是否在列表中堡距，并對相同值的情況做處理
# for i in nums:
# if (target - i) in nums:
# if i == (target - i):
# return [nums.index(i), nums.index(i, nums.index(i)+1)]
# else:
# return [nums.index(i), nums.index(target-i)]
# 上述方法3有漏洞：相同的值被取了兩次實際卻只有一個，遇到[3,2,4]就歇菜了兆蕉，i=3沒有兩個3返回null
# 方法4：基于方法3羽戒，加一個符合條件的數(shù)值數(shù)量的判斷，彌補漏洞
# for i in nums:
# if (target - i) in nums:
# if i == (target - i) and nums.count(i) > 1:
# return [nums.index(i), nums.index(i, nums.index(i)+1)]
# else:
# return [nums.index(i), nums.index(target-i)]
# 上述方法4還是有漏洞虎韵，遇到[3,2,4]沒有歇菜半醉，但是返回了[0,0]，判斷條件沒搞清楚邏輯劝术，畫NS圖自救，
# 發(fā)現(xiàn)是漏掉了i==(target-i) and .count(i)<1 這一類情況呆奕，應(yīng)當continue养晋，而不是直接進上述的else
# 方法5：基于方法3和方法4，圍繞不能復(fù)用的條件梁钾，進行兩層判斷：先挖坑绳泉，再網(wǎng)魚，步驟有先后手
for i in nums:
if (target - i) in nums:
if i == (target-i):
if nums.count(i) > 1:
return [nums.index(i), nums.index(i, nums.index(i)+1)]
else:
return [nums.index(i), nums.index(target-i)]
# 成功accepted了姆泻！
# Runtime: 788 ms, faster than 35.47% of Python3 online submissions for Two Sum.
# Memory Usage: 13.8 MB, less than 70.43% of Python3 online submissions for Two Sum.
上述方法小結(jié)
- 總體思路混亂零酪，語無倫次，可悲拇勃。
- 冷靜一下四苇，算法的思路主要分兩大類：
2.1 直接查找計算法（找到一個i和一個j，判斷相應(yīng)和是否為target）方咆；
2.2 間接查找問詢法（找到一個i月腋，再判斷target與i的差值是否存在）。 - 再冷靜一下瓣赂，查找的思路主要分兩大類：
3.1 基于item
3.2 基于index
綜上榆骚，在已有的認知范圍內(nèi)，理論上有四個方法可以解決LeetCode這個“Two Sum”的問題煌集，分別是：
(1) 基于item的直接查找計算法
for i in nums:
for j in nums:
# find it!
if (i+j)==target:
# maybe twice?
if i==j:
# more than 1 elements!
if nums.count(i)>1:
# don't forget find the 2nd one's index
return [nums.index(i), nums.index(i, nums.index(i)+1)]
# not twice
else:
return [nums.index(i), nums.index(j)]
果然凹酥！成功苫纤！
Runtime: 4604 ms, faster than 25.25% of Python3 online submissions for Two Sum.
Memory Usage: 13.8 MB, less than 68.81% of Python3 online submissions for Two Sum.
(2) 基于index的直接查找計算法
for i in range(len(nums)):
for j in range(len(nums)):
if (nums[i]+nums[j])==target:
if i==j:
if nums.count(nums[i])>1:
return [i, nums.index(nums[i], i+1)]
else:
return [i, j]
果然暗锬啤纲缓！成功！就是慢了點放钦。
Runtime: 7688 ms, faster than 5.01% of Python3 online submissions for Two Sum.
Memory Usage: 13.8 MB, less than 73.03% of Python3 online submissions for Two Sum.
(3) 基于item的間接查找問詢法
for i in nums:
if (target-i) in nums:
if i == (target-i):
if nums.count(i)>1:
return [nums.index(i), nums.index(i, nums.index(i)+1)]
else:
return [nums.index(i), nums.index(target-i)]
果然吧恰！成功操禀！快了不少褂策。
Runtime: 776 ms, faster than 37.75% of Python3 online submissions for Two Sum.
Memory Usage: 13.8 MB, less than 67.25% of Python3 online submissions for Two Sum.
(4) 基于index的間接查找問詢法
for i in range(len(nums)):
if (target - nums[i]) in nums:
if i==nums.index(target-nums[i]):
if nums.count(nums[i])>1:
return [i, nums.index(nums[i], i+1)]
else:
return [i, nums.index(target-nums[i])]
果然啊颓屑！成功斤寂！保持在高水準。
Runtime: 788 ms, faster than 35.47% of Python3 online submissions for Two Sum.
Memory Usage: 13.7 MB, less than 85.58% of Python3 online submissions for Two Sum.
做一個回顧
首先恭喜自己揪惦，順利通關(guān)遍搞。分數(shù)還行，Top 65%的位置器腋，770ms溪猿，13.8MB，拿到了一顆星纫塌。
上述的四個方法诊县，不管是“一手抓一手再抓”，還是“一手抓一手在摸”措左，在具體比較的時候都是“憑空”的依痊，沒有放在一個籃子或者秤上進行操作，總而言之就是有不可控的黑洞怎披。
字典dictionary是一個比較喜歡的籃子胸嘁。此外，幾年前看過一個蹺蹺板的方法凉逛，結(jié)合起來：
(5) 基于item的字典dict蹺蹺板
dict = {}
for i in nums:
if i in dict.keys():
if i == dict.get(i):
return [nums.index(i), nums.index(i, nums.index(i)+1)]
else:
# follow the queue number
return [nums.index(dict.get(i)), nums.index(i)]
else:
dict.update({target-i: i})
厲害了性宏！成功！
Runtime: 36 ms, faster than 94.69% of Python3 online submissions for Two Sum.
Memory Usage: 14.2 MB, less than 50.40% of Python3 online submissions for Two Sum.
(6) 基于index的字典dict蹺蹺板
dict = {}
for i in range(len(nums)):
if nums[i] in dict.keys():
# ensure index return by the same number
if i == nums.index(dict.get(nums[i])):
return [i, nums.index(dict.get(nums[i]), i+1)]
else:
# follow the queue number
return [nums.index(dict.get(nums[i])), i]
else:
dict.update({target-nums[i]: nums[i]})
厲害了状飞！不如上面的簡潔衔沼。
Runtime: 40 ms, faster than 87.10% of Python3 online submissions for Two Sum.
Memory Usage: 14.2 MB, less than 53.05% of Python3 online submissions for Two Sum.
對比一下，新的分數(shù)還行昔瞧，Top 5%的位置指蚁，36ms，14.2MB自晰。
寫在最后
最重要的測試集凝化，用例，三個有代表性的列表酬荞，以及目標值：
[2, 7, 11, 15]
9
[3, 3]
6
[3, 2, 4]
6
第二波的對比第一波：排名從前63到了前5搓劫，耗時從776ms到36ms瞧哟，內(nèi)存從13.8MB到14.2MB。
最后的最后枪向，剩下的幾種解法呢勤揩？
簡單來說，就是暴利查找的時候秘蛔，第二層循環(huán)index下標從i+1開始霸赏觥！具體示例如下：
(7) 基于index的直接切片查找法
for i in nums:
for j in nums[nums.index(i):]:
# find it!
if (i+j)==target:
# maybe twice?
if i==j:
# more than 1 elements!
if nums.count(i)>1:
# don't forget find the 2nd one's index
return [nums.index(i), nums.index(i, nums.index(i)+1)]
# not twice
else:
return [nums.index(i), nums.index(j)]
成功深员！比原來的速度略有提升负蠕。
Runtime: 3856 ms, faster than 26.13% of Python3 online submissions for Two Sum.
Memory Usage: 13.7 MB, less than 85.58% of Python3 online submissions for Two Sum.
(8) 基于index的間接切片問詢法
for i in range(len(nums)):
# begin from i's index + 1, hope more and faster
if (target - nums[i]) in nums[i+1:]:
if i==nums.index(target-nums[i]):
if nums.count(nums[i])>1:
return [i, nums.index(nums[i], i+1)]
else:
return [i, nums.index(target-nums[i])]
成功！但是速度并沒有蹺蹺板的快倦畅。
Runtime: 836 ms, faster than 33.40% of Python3 online submissions for Two Sum.
Memory Usage: 13.8 MB, less than 66.48% of Python3 online submissions for Two Sum.
有幾點需要說明：
- 忽略從i+1開始遮糖，是因為直接被[3,3]帶歪思路了，看來用例有時候也是把雙刃劍叠赐。得瑟啥欲账？可悲。
- 第一次遇見蹺蹺板的時候芭概，驚為天人赛不，現(xiàn)在沒那么驚嚇了，還是贊嘆谈山。天外有天，山外有山宏怔。
- 原本以為加了i+1開始奏路，找的越來越快，能跟蹺蹺板比一比臊诊。發(fā)現(xiàn)還是差了檔次鸽粉，應(yīng)是dict的硬傷。
- 雖然說有8個解法抓艳，其實核心思想是這幾個：暴力查找触机、差值問詢、臨時存取玷或、縮減范圍儡首。
- 文中引用的數(shù)據(jù)應(yīng)該不精準，看個定性就好偏友。游戲也挺好玩的蔬胯。
