問題:
給定一個數(shù)和一個數(shù)列,找到這個數(shù)列中某兩個元素之和為給定的數(shù)浙值,返回這兩個數(shù)的 index
代碼
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i,num in enumerate(nums):
sub_num = target-num
if sub_num in nums:
j = nums.index(sub_num)
if j<i:
return [i,j]
思路:
1.自然而然地想到暴力破解的思路们豌,易得是 O()的時間復(fù)雜度交惯,嘗試了一下,時間超過了
2.時間不夠变秦,那就空間換時間成榜,用 hashmap 的思路,會得到時間復(fù)雜度和空間復(fù)雜度都是 O(n)的解法
Note:
- enumerate 函數(shù):enumerate(sequence,[start]=0)指定一個迭代器和一個初始位置(下標)蹦玫,返回一個枚舉對象(enumerate)
- index函數(shù):list.index(object)返回list 中第一個 object所在的索引赎婚,注意是第一個,所以 line 12的<可以改成!=樱溉,但不能改成>惑淳。舉例,nums=[3,3],target=6饺窿。
- python的字典是用哈希實現(xiàn)的歧焦,所以用 enumerate 會返回一個字典- [ ]