代码git：History for 1. 两数之和.py - WankkoRee/LeetCodeAnswersWithPython3
为了明年的就业面试，所以准备刷题了，而力扣是出了名的笔试黄埔军校，所以就来刷力扣的题了。
从第一题来看，力扣对于各种边角条件的数据准备得还挺充分的，而且还能查看时空排名，整挺好。
刚开始看到这题，第一思路是遍历一次数据，然后每次算出另一个数是多少，判断下这个数是不是在数据里，在的话就返回俩数下标。（两重for的O(n ^ 2)压根没考虑）
所以就写出了这么个玩意。
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i, x in enumerate(nums):
y = target - x
if y in nums:
return [i, nums.index(y)]
solution = Solution()
print(solution.twoSum([2,7,11,15], 9))然后就理所当然地err了，因为没考虑自身就是另一半的情况，具体数据是solution.twoSum([3,2,4], 6)，于是就写了个数据相等就跳过的额外判断。
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i, x in enumerate(nums):
y = target - x
if y == x:
continue
if y in nums:
return [i, nums.index(y)]
solution = Solution()
print(solution.twoSum([2,7,11,15], 9))
print(solution.twoSum([3,2,4], 6))然后还是理所当然地err，因为题目来了个solution.twoSum([3,3], 6)，结果我的代码压根不返回东西了，因为按我的代码逻辑，这种重复出现的情况压根就没考虑过，于是那就推翻刚才的额外判断，直接改改另一个数的可查范围呗，然后就被数据给误导了写出个去掉首位的憨批代码。
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i, x in enumerate(nums):
y = target - x
if y in nums[1:]:
return [i, nums[1:].index(y) + 1]
solution = Solution()
print(solution.twoSum([2,7,11,15], 9))
print(solution.twoSum([3,2,4], 6))
print(solution.twoSum([3,3], 6))所以这个代码肯定没过，卡的数据是solution.twoSum([2,5,5,11], 10)，得把数据裁剪成当前位之后的半段数据才行，于是接着冲。
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i, x in enumerate(nums):
y = target - x
if y in nums[i + 1:]:
return [i, nums[i + 1:].index(y) + 1]
solution = Solution()
print(solution.twoSum([2,7,11,15], 9))
print(solution.twoSum([3,2,4], 6))
print(solution.twoSum([3,3], 6))
print(solution.twoSum([2,5,5,11], 10))这个代码我本地测都没测就冲了，因为感觉没啥边缘情况没考虑到了，必拿下！结果就在历史数据翻车了，solution.twoSum([3,2,4], 6)都没过，本地看了下原来是另一个数的下标我只+1，而不是+i+1，我的锅。
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i, x in enumerate(nums):
y = target - x
if y in nums[i + 1:]:
return [i, nums[i + 1:].index(y) + i + 1]
solution = Solution()
print(solution.twoSum([2,7,11,15], 9))
print(solution.twoSum([3,2,4], 6))
print(solution.twoSum([3,3], 6))
print(solution.twoSum([2,5,5,11], 10))终于过了所有数据，这第一题数据就这么离谱，有点期待后面的了。
执行用时：
468 ms, 在所有Python3提交中击败了43.32%的用户
内存消耗：15.1 MB, 在所有Python3提交中击败了85.64%的用户
通过测试用例：55 / 55
一觉睡醒尝试用空间换时间，把需要重复使用的值都给赋变量，然后时间确实小了一点，但是内存也大了一点。
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i, x in enumerate(nums):
y = target - x
p = nums[i + 1:]
if y in p:
return [i, p.index(y) + i + 1]
solution = Solution()
assert solution.twoSum([2,7,11,15], 9) == [0, 1]
assert solution.twoSum([3,2,4], 6) == [1, 2]
assert solution.twoSum([3,3], 6) == [0, 1]
assert solution.twoSum([2,5,5,11], 10) == [1, 2]执行用时：
376 ms, 在所有Python3提交中击败了46.37%的用户
内存消耗：15.2 MB, 在所有Python3提交中击败了75.08%的用户
通过测试用例：55 / 55
所以说应该是我这个思路差不多到极限了，那些同语言的其他人应该是另外的思路去解的（总不会有人搞针对数据的憨批输出脚本吧）。
于是打算将空间换时间进行到底，把数据的值和下标开个dict映射起来，然后原本数据的话因为不用管重复的情况了（已经可以在映射里表示出来了），所以就直接优化成set（in查找时set会比list快很多），然后再遍历的时候考虑下重复等特殊情况，大概思路就完事了，结果直接几乎重构了整个代码。
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums_ = {}
for i, d in enumerate(nums):
if d not in nums_.keys():
nums_[d] = [i]
else:
nums_[d].append(i)
nums = set(nums)
for x in nums:
y = target - x
if y in nums and (x != y or len(nums_[y]) >= 2):
return [nums_[x][0], nums_[y][-1]]
solution = Solution()
assert solution.twoSum([2,7,11,15], 9) == [0, 1]
assert solution.twoSum([3,2,4], 6) == [1, 2]
assert solution.twoSum([3,3], 6) == [0, 1]
assert solution.twoSum([2,5,5,11], 10) == [1, 2]执行用时：
40 ms, 在所有Python3提交中击败了62.76%的用户
内存消耗：17.1 MB, 在所有Python3提交中击败了5.09%的用户
通过测试用例：55 / 55
Comments NOTHING