文/良宵听雨。授权“游戏夜读”发表。
打开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]:
开始答题……其他略。题目中有两个假设：
1 有且仅有一个解；
2 同一个元素不能被使用两次。
尝试的5种方法，失败了4次
# 方法1：循环遍历列表中的数，一个一个找
# 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，循环遍历列表的索引，这样就避免数值相同的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：根据题目中说的假设（恰有一个答案），直接匹配差值是否在列表中，并对相同值的情况做处理
# 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，加一个符合条件的数值数量的判断，弥补漏洞
# 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图自救，
# 发现是漏掉了i==(target-i) and .count(i)<1 这一类情况，应当continue，而不是直接进上述的else
# 方法5：基于方法3和方法4，围绕不能复用的条件，进行两层判断：先挖坑，再网鱼，步骤有先后手
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.
上述方法小结
总体思路混乱，语无伦次，可悲。
冷静一下，算法的思路主要分两大类：
2.1 直接查找计算法（找到一个i和一个j，判断相应和是否为target）；
2.2 间接查找问询法（找到一个i，再判断target与i的差值是否存在）。
再冷静一下，查找的思路主要分两大类：
3.1 基于item
3.2 基于index
综上，在已有的认知范围内，理论上有四个方法可以解决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.
做一个回顾
首先恭喜自己，顺利通关。分数还行，Top 65%的位置，770ms，13.8MB，拿到了一颗星。
上述的四个方法，不管是“一手抓一手再抓”，还是“一手抓一手在摸”，在具体比较的时候都是“凭空”的，没有放在一个篮子或者秤上进行操作，总而言之就是有不可控的黑洞。
字典dictionary是一个比较喜欢的篮子。此外，几年前看过一个跷跷板的方法，结合起来：
(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.
对比一下，新的分数还行，Top 5%的位置，36ms，14.2MB。
写在最后
最重要的测试集，用例，三个有代表性的列表，以及目标值：
[2, 7, 11, 15]
9
[3, 3]
6
[3, 2, 4]
6
第二波的对比第一波：排名从前63到了前5，耗时从776ms到36ms，内存从13.8MB到14.2MB。
最后的最后，剩下的几种解法呢？
简单来说，就是暴利查找的时候，第二层循环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]带歪思路了，看来用例有时候也是把双刃剑。得瑟啥？可悲。
第一次遇见跷跷板的时候，惊为天人，现在没那么惊吓了，还是赞叹。天外有天，山外有山。
原本以为加了i+1开始，找的越来越快，能跟跷跷板比一比。发现还是差了档次，应是dict的硬伤。
虽然说有8个解法，其实核心思想是这几个：暴力查找、差值问询、临时存取、缩减范围。
文中引用的数据应该不精准，看个定性就好。游戏也挺好玩的。
评论