LeetCode 面试题 16.24. 数对和
题目描述
题意分析
从数组中找出尽可能多的数对，使每对之和等于
target，每个元素下标最多使用一次。相同数值的不同元素可以分别配对，答案中的数对数值也可以重复；不能把问题变成对数值去重后只找一组答案。
解法：未配对频次表
核心思路
[!blue]
对当前值
x，能配对的数值只有y = target - x。用cnt[v]表示扫描过的元素中，值为v且尚未进入答案的数量。读到x后，若已有未使用的y，立即消耗其中一个并输出数对；否则将当前x留在表中，等待后续补数。立即配对不会减少最终数量。对于不同的互补值
x、y，所有配对都只能各取一个，最多组成两类元素数量的较小值。算法不会让两类未配对元素同时剩下，因此扫描结束时必然达到这个上限。若x = y，则每两个这样的元素组成一对，至多剩下一个，也达到该类的最大对数。每次先查询历史频次，再决定是否存入当前值，所以配对的是当前下标与此前的另一个下标，不会用同一元素配自己。配对成功后消耗一个历史计数，当前元素也不再入表，保证两者以后都不会复用。
Java 在计数降到零时删除键，因此
containsKey(y)就等价于还有可用补数；Go 保留零计数，但用cnt[y] > 0判断，两种实现维护的是同一个剩余频次含义。
解题步骤
- 初始化空频次表和答案列表。
- 顺序读取
x，计算唯一补数y = target - x。- 若历史中还有
y，输出[x, y]并消耗一个y；否则将cnt[x]加 1。- 继续扫描全部元素后返回结果。剩余元素已经无法互相组成合法数对，无需继续处理。
代码实现
class Solution {
public List<List<Integer>> pairSums(int[] nums, int target) {
Map<Integer, Integer> cnt = new HashMap<>();
List<List<Integer>> answer = new ArrayList<>();
for (int x : nums) {
int y = target - x;
if (cnt.containsKey(y)) {
answer.add(List.of(x, y));
if (cnt.merge(y, -1, Integer::sum) == 0) {
cnt.remove(y);
}
} else {
cnt.merge(x, 1, Integer::sum);
}
}
return answer;
}
}
func pairSums(nums []int, target int) (answer [][]int) {
cnt := map[int]int{}
for _, x := range nums {
y := target - x
if cnt[y] > 0 {
cnt[y]--
answer = append(answer, []int{
x,
y,
})
} else {
cnt[x]++
}
}
return
}
复杂度分析
- 时间复杂度：期望 $O(n)$。每个元素只查询、更新常数次哈希表，最多输出
n/2对。- 空间复杂度：$O(n)$。未配对频次表最坏保存线性个不同值，返回结果也最多包含线性个元素。
关键点总结
[!green]
- 补数唯一，使每个数值只参与一类配对，立即匹配就能达到最大对数。
- 频次保存的是剩余可用元素数量，不是是否曾经出现。
- 查询历史发生在当前值入表之前，补数等于自身时也不会复用当前下标。
- 算法只读输入数组，不需要排序。
易错点总结
[!yellow]
- 只用集合记录数值，会丢失相同值还有多少个可用元素的信息。
- 配对后不减少频次，会把同一个历史下标反复加入答案。
- 先将当前值加入表再查补数，可能在
target = 2 * x时让元素与自己配对。- 找到第一对就返回，会漏掉其余仍能组成的数对。
- Java 使用键存在性判断时必须删除零计数键，否则会把已经消耗完的补数当作仍然可用。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1. 两数之和 | 简单 | 原题只找一对且通常返回下标，本题要持续消耗频次并输出不重用元素的全部数对。 |
| 167. 两数之和 II - 输入有序数组 | 中等 | 排序后可用双指针找互补值，本题重复命中后必须同时消耗两个位置。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！