LeetCode 面试题 16.24. 数对和
目录
题目描述
题意分析
从数组中找出尽可能多的两两不重叠数对，使每对之和等于 target。每个元素下标只能使用一次，重复值代表不同元素，可以分别参与配对。
排序后双指针可以做，但要
O(n log n)且会改变顺序。哈希表能在一次扫描中记录“已经见过但尚未配对”的元素频次。对当前值 x，唯一能与它配对的是
y=target-x。若之前还有未使用的 y，就立刻消耗一个并输出该对；否则把 x 留给未来。由于 x 没有第二种互补选择，立即配对不会损失更优方案。
解法：未配对频次表
核心思路
哈希表
count[v]的不变量是：扫描过的前缀中，值为 v 且尚未进入任何答案数对的元素个数。读到 x 时先查补数 y。若
count[y]>0，当前 x 与其中一个 y 配对，并将计数减一；否则count[x]++。每次输出恰好消耗两个不同下标。例：
nums=[5,6,5,6]、target=11。第一个 5 暂存；读 6 时消耗 5 得一对；第二个 5 再暂存；最后一个 6 再消耗一次，得到两对。重复值不会被集合去重。对
nums=[1,1,1]、target=2，第二个 1 与第一个配成一对，第三个 1 留在表中，正确得到一对而不是把同一元素复用。
解题步骤
- 初始化空频次表与答案列表。
- 依次读取 x，计算
y=target-x。- 若 y 的未配对频次大于 0，频次减一并加入
[x,y]。- 否则把 x 的未配对频次加一。
- 扫描结束返回所有数对。
代码实现
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)，每个元素只做常数次哈希操作。- 空间复杂度：
O(n)，最坏没有任何元素能配对，全部留在频次表；返回结果最多也有n/2对。
关键点总结
- map 存频次而不是布尔值，才能正确处理重复元素。
- 必须先查补数再决定是否保存当前值；补数等于自身时也不会把当前元素和自己配对。
- 成功配对后消耗一个计数，保证每个下标最多使用一次。
- 面试追问若允许排序，可给出双指针
O(n log n)时间、除排序外O(1)空间的方案；哈希版保留输入顺序且平均线性。
易错点总结
- 错误写法：用 Set 记录已见值。反例
[1,1,1,1]、target=2 应产生两对，集合无法表示还剩几个 1。- 配对后不减频次：
[1,2,2]、target=3 会把唯一的 1 与两个 2 都配对，复用了同一下标。- 先把 x 加入表再检查补数：当
target=2x时，单个元素就会和自己配对。反例nums=[3]、target=6 应返回空。- 找到第一对就返回：题目要所有可组成的数对，不是任意一对。
- 排序双指针命中后只移动一侧：另一侧元素会被再次使用；成功时左右指针必须同时收缩。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1. 两数之和 | 简单 | 返回一组下标，不允许复用元素 |
| 167. 两数之和 II | 中等 | 有序数组上的双指针 |
| 1679. K 和数对的最大数目 | 中等 | 与本题同构，求数对数量 |