题目描述

[EN | CN]

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

你可以假设 每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

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

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

解法 1:哈希表

暴力解法两两配对显然是 $O(n^2)$ 复杂度。

既然涉及 搜索匹配,就考虑一下 hash,那么思路就简单了,只要建立哈希表(字典)存储从 value 到 index 的映射,然后遍历数组,对于每一个 num 都在字典中找是否存在其补数(target - num)即可。

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(n)$,需要遍历一遍;
  • 空间复杂度为 $O(n)$,需要存储跟原数组长度相同的哈希表。

实现如下:

1
2
3
4
5
6
7
8
9
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        val_to_idx = dict()
        for i, num in enumerate(nums):
            diff = target - num
            if diff in val_to_idx:
                return val_to_idx[diff], i
            else:
                val_to_idx[num] = i

结果:

  • 执行用时:44 ms,在所有 Python3 提交中击败了 85.40% 的用户。
  • 内存消耗:14.9 MB,在所有 Python3 提交中击败了 5.12% 的用户。