LeetCode-001:两数之和

两数之和 - 力扣(LeetCode)

关键算法

  • 对于Python来说,集合和字典其实都是利用哈希实现的,所以说集合和字典的搜索速度比列表快很多
  • 利用字典,键是数字,值是索引
  • 使用enumerate函数可以取出列表的索引和值
  • 声明一个空字典,遍历整个列表,查看目标值和每个数的差值是否在字典中,如果在则返回该数差值和该数的索引,如果不在的话则将该数的值作为键、索引作为值放入字典中

代码实现

时间复杂度:O(n),空间复杂度:O(n)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        counter = {}
        for i, n in enumerate(nums):
            choice = target - n
            if choice in counter:
                return [i, counter[choice]]
            counter[n] = i