LeetCode | 两数之和

题目#

给定一个整数数组 nums 和一个整数 target，需要找出数组中两个不同位置的元素，使它们的和等于 target，并返回这两个元素的下标。

题目保证每组输入恰好存在一个答案。同一个元素不能使用两次。返回的两个下标顺序通常不重要。

示例：

1
输入: nums = [2, 7, 11, 15], target = 9
2
输出: [0, 1]
3
原因: nums[0] + nums[1] = 2 + 7 = 9

1
输入: nums = [3, 2, 4], target = 6
2
输出: [1, 2]

1
输入: nums = [3, 3], target = 6
2
输出: [0, 1]

讲解#

目标是找两个数，它们相加等于 target。

最直接的做法是两层循环，把所有组合都试一遍。时间复杂度是 O(n^2)，空间复杂度是 O(1)。

更好的做法是用字典记录已经见过的数字。Python 的字典就是一种哈希表，可以理解成“快速查找表”，这里保存的是：

1
数字 -> 下标

当遍历到当前数字 num 时，只需要看字典里有没有 target - num。如果有，这两个数就正好组成答案。

哈希表会根据要查的数字快速定位位置，不是像列表那样从头到尾一个个比较。need in seen 查的是字典，平均查找复杂度是 O(1)，所以不会把整体复杂度变回 O(n^2)。

关键点是：先查需要的数，再记录当前数。这样不会把同一个元素用两次。

复杂度：

• 暴力做法：时间复杂度 O(n^2)，空间复杂度 O(1)
• 字典做法：时间复杂度 O(n)，空间复杂度 O(n)

代码#

1
class Solution:
2
    def twoSum(self, nums: List[int], target: int) -> List[int]:
3
        _hash = {}
4

5
        for i,num in enumerate(nums):
6
            find = target - num
7
            if( find in _hash ):
8
                return [_hash[find],i]
9
            _hash[num] = i
10
        return []

1
from src.python._001_Two_Sum import Solution
2

3

4
sol = Solution()
5
assert sol.twoSum([2, 7, 11, 15], 9) == [0, 1]
6
assert sol.twoSum([3, 2, 4], 6) == [1, 2]
7
assert sol.twoSum([3, 3], 6) == [0, 1]
8

9
print("PASS")

参考资料#

• LeetCode 原题：https://leetcode.com/problems/two-sum/
• 力扣官方题解：https://leetcode.cn/problems/two-sum/solutions/434597/liang-shu-zhi-he-by-leetcode-solution/