题目难度: 中等
原题链接[1]
题目描述今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
设计一个算法,找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。
示例 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参考资料[1]
原题链接: https://leetcode-cn.com/problems/pairs-with-sum-lcci/



