[数据结构与算法]两数之和——python

两数之和—python

方法一：暴力枚举
搜寻target-num[i] = x 在nums中是否有匹配项
复杂度O（n^2）

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        
        return []

方法二：哈希
python中字典运用了哈希表，可以用字典来做.基本思想和法一差不多，但是用哈希表节省时间

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()#创建字典
        '''
        enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标
        例：>>seasons = ['Spring', 'Summer', 'Fall', 'Winter']
		    >>list(enumerate(seasons))
			>>[(0, 'Spring'), (1, 'Summer'), (2, 'Fall'), (3, 'Winter')]
        '''
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []