题目难度: 中等
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
设计一个算法，找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。
示例 1:
- 输入: nums = [5,6,5], target = 11
- 输出: [[5,6]]
示例 2:
- 输入: nums = [5,6,5,6], target = 11
- 输出: [[5,6],[5,6]]
提示：
- nums.length <= 100000
题目思考
- 给定一个数字, 如何快速找到和为指定值的另一个数字?
- 使用了一个数字之后, 如何避免重复使用它?
解决方案
思路
- 分析题目, 要想快速得到满足要求的数字对, 很容易想到使用哈希表这种数据结构存储所有数字, 这样对于每个数字 x, 都可以在常数时间内判断哈希表中是否存在 target-x
- 由于题目要求原数组的每个数字都可以使用一次, 所以这里使用计数字典来存储所有数字以及其出现次数
- 这样对于数字 x 而言, 假设它出现了 a 次, 而 target-x 出现了 b 次, 则有效数字对的数目分为以下情况:
target-x > x: 有效数字对的数目就是 min(a,b)target-x = x: 有效数字对的数目就是 floor(a/2)target-x < x: 忽略这种情况, 否则就与处理 target-x 时的情况 1 重复了
- 下面的代码对必要步骤有详细的解释, 方便大家理解
复杂度
- 时间复杂度
O(N): 每个数字最多遍历两次 - 空间复杂度
O(N): 使用额外的计数字典存储 N 个数字
代码
class Solution:
def pairSums(self, nums: List[int], target: int) -> List[List[int]]:
# 统计每个数字的出现次数
cnts = collections.Counter(nums)
res = []
for x in cnts:
y = target - x
if y in cnts and y >= x:
# 可以凑成对的另一个数字也在字典中, 且那个数字不小于当前数字(避免重复选取)
if y > x:
# 两个数字不等时, 取较小的计数作为数对的数目
cnt = min(cnts[x], cnts[y])
else:
# 两个数字相等时, 每个数对使用两个数字, 所以数对数目是当前计数的一半(向下取整)
cnt = cnts[x] // 2
res += [[x, y]] * cnt
return res
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号