two sum python_Python | Leetcode 之 Two Sum

说来惭愧，到现在才开始刷Leetcode，但迟到总比不到好。

题目：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 sameelement twice.

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

先上暴力解法：

class Solution:

def twoSum(self, nums: List[int], target: int) -> List[int]:

length = len(nums)

for i in range(length) :

for j in range(length):

if nums[i] == target - nums[j] and i != j:

return [i, j]

Submit看结果：

Runtime: 7780 ms, faster than 5.01% of Python3 online submissions for Two Sum.

Memory Usage: 13.8 MB, less than 24.07% of Python3 online submissions for Two Sum.

即使是第一道题，但这结果也太差了吧

两个for循环做了无用功，如果把list分成两部分来计算，也就是只用for循环一次呢？

class Solution:

def twoSum(self, nums: List[int], target: int) -> List[int]:

k = 0

for i in nums:

k += 1

if target - i in nums[k:]:

return(k -1, nums[k:].index(target - i) + k)

Submit看结果：

Runtime: 848 ms,faster than32.81%ofPython3online submissions forTwo Sum.

仍旧是连一半都没超过啊，娘匹西。

官方方法 Two-Pass Hash Table

class Solution:

def twoSum(self, nums: List[int], target: int) -> List[int]:

hashTable = {}

length = len(nums)

for i in range(length):

hashTable[nums[i]] = i

for i in range(length):

if target - nums[i] in hashTable and hashTable[target - nums[i]] != i:

return [i, hashTable[target - nums[i]]]

return([])

Submit看结果：

Runtime: 48 ms, faster than58.71%ofPython3online submissions forTwo Sum.

官方还提供One-Pass Hash Table，也就是每次插入一个元素，然后检查这个元素是否符合，以此类推。

class Solution:

def twoSum(self, nums: List[int], target: int) -> List[int]:

hashTable = {}

for i, num in enumerate(nums):

if target - num in hashTable:

return([hashTable[target - num], i])

break

hashTable[num] = i

return([])

但这个结果submit的结果并没有表现得如官方所说的那样。

总结：结果这个问题的方法有很多，从暴力到哈希表，除了要熟知基本的元素操作，便是懂得时间复杂度和空间复杂度的一个balance

关于Python语法的细节还是要加强，不然卡住的地方太多了

哈希表的概念要再加强一些