Skip to content

两数之和

梦开始的地方

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

暴力枚举

最简单的做法就是双重循环：

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

这时候的时间复杂度是：$\mathcal{O}(N^2)$，空间复杂度是：$\mathcal{O}(1)$

哈希表

我们还可以用空间换时间：

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

在遍历的过程中维护一个哈希表，可以查询已经遍历过的所有值。

这样一来时间复杂度就降低到了：$\mathcal{O}(N)$

不过空间复杂度上升到了：$\mathcal{O}(N)$

Last update: 2025-04-07 14:46:13
Created: 2025-04-07 14:46:13

Comments