Skip to content

1. Two Sum 两数之和

难度: Easy

刷题内容

原题连接

  • https://leetcode.com/problems/two-sum
  • https://leetcode-cn.com/problems/two-sum

内容描述

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题方案

思路 1

我们在找两个的和是否等于某一个值。

如果是两两组合的笛卡尔积，相当于闭着眼碰运气，时间复杂度为: O(n^2)

例如: 

* 2+7     2+11    2+15
* 7+11    7+15
* 11+15

思路 2

如果我们换一种方式: target - 当前数字, 需要的另外一个变量就变成已知！

  1. 通过字典(哈希 Hash)对nums建立词库表 loopup, 时间复杂度是 0(n)
  2. 判断差值是否存在 lookup 中, 时间复杂度是 0(1)
  3. 所以最后的结果就是: O(n) * O(1) = O(n)
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        lookup = {}
        for i, num in enumerate(nums):
            if target - num in lookup:
                # 为什么先后顺序是 lookup[target - num], i
                # 因为当前是i，而差值只能从 lookup 中找，而 lookup 是在 i 之前面入库的
                # 所以 顺序是 lookup[target - num], i
                return [lookup[target - num],i]
            lookup[num] = i
        return []


if __name__ == "__main__":

    nums = [2, 7, 11, 15]
    target = 9
    so = Solution()
    n = so.twoSum(nums, target)
    print("结果: ", n)
回到顶部