LeetCode 1679. K 和数对的最大数目
题目描述
题意分析
每次从数组中选出两个和为
k的元素并移除，求最多能够执行多少次。每个数组位置只能使用一次，返回的是配对数量，不是移除元素总数。相同数值来自不同位置时可以分别参与配对，但一个元素不能与自己配对。若
2 * x == k，也必须找到两个不同位置的x才能完成一次操作。数组只有一个元素或没有互补值时，答案为零。关键限制是补数唯一：值为
x的元素只能和值为k - x的元素配对。因此不同互补值组不会争抢同一个元素，不需要采用一般图上的匹配算法。每组内部尽可能配完，再相加就是全局最大数量。
解法一：哈希表边遍历边配对
核心思路
[!blue]
用哈希表
need保存已经遍历过、但尚未配对的元素数量。读到当前值x后，先查询补数want = k - x：如果还有可用补数，就消耗一个补数并把答案加一；否则把当前x的可用数量加一，等待后面的元素。表中存的是剩余可用数量，而不是历史出现总数。配对成功后立即减一，保证已经使用的旧元素不会再次参与；当前元素配对成功后也不再加入表中。查询发生在登记当前元素之前，所以即使补数与当前值相同，也只能找到此前另一个位置的元素，不会与自己配对。
见到可配对象就立即配对为什么最优？对于两个不同的互补值，每一边的元素对另一边都完全等价，最多只能组成两边数量的较小值。在线配对会持续消耗两边，直到数量少的一边用完，恰好达到这个上界。补数与自身相同时，每两个不同位置配成一对，最终得到该值出现次数除以二向下取整，也达到上界。
各互补组互不影响，这些局部最大数量就能共同组成全局最优答案。计数归零的键可以留在表里，但查找时必须判断值大于零，不能只判断键是否存在。
解题步骤
- 初始化空哈希表
need，答案ans = 0。- 遍历当前值
x，计算唯一补数want = k - x。- 若
need[want] > 0，将其减一，答案加一；当前元素也在这次配对中消耗。- 否则令
need[x]加一，登记为等待配对的元素。- 返回配对次数，未匹配的剩余元素不计入答案。
代码实现
class Solution {
public int maxOperations(int[] nums, int k) {
// need 的语义：值 -> 还剩几个该值的元素在等待配对
Map<Integer, Integer> need = new HashMap<>();
int ans = 0;
for (int x : nums) {
int want = k - x;
int count = need.getOrDefault(want, 0);
if (count > 0) {
// 前面有个还没配上的补数在等，当场配成一对并消耗掉它
need.put(want, count - 1);
ans++;
} else {
// 暂时无人可配，x 自己进等待池；查询在记账之前，所以配不到自己
need.put(x, need.getOrDefault(x, 0) + 1);
}
}
return ans;
}
}
func maxOperations(nums []int, k int) int {
// need 的语义：值 -> 还剩几个该值的元素在等待配对
need := make(map[int]int)
ans := 0
for _, x := range nums {
want := k - x
if need[want] > 0 {
// 前面有个还没配上的补数在等，当场配成一对并消耗掉它
need[want]--
ans++
} else {
// 暂时无人可配，x 自己进等待池；查询在记账之前，所以配不到自己
need[x]++
}
}
return ans
}
复杂度分析
- 时间复杂度：期望 $O(n)$，每个元素进行常量次哈希查询和更新。
- 空间复杂度：$O(n)$，最坏需要保存所有不同值的待配计数，零计数键也可能继续保留。
关键点总结
[!green]
need只表示未使用的元素数量，配成一对就同时消耗旧补数和当前元素。- 先查询、失败后才登记，保证配对来自两个不同位置。
- 补数唯一且同值元素可互相替代，使立即配对能够达到每组的数量上界。
解法二：排序后双指针对撞
核心思路
[!blue]
先升序排序，用
left和right指向剩余区间的最小值与最大值，根据两端之和与k的关系决定动作。已经处理的区间外元素，要么完成配对，要么已经证明无法在剩余范围里找到补数。若两端之和小于
k，左端即使配上最大的右端也不够，配上其他更小的数只会更小，所以左端不可能参与任何剩余合法配对，可以令left++。若两端之和大于k，右端即使配上最小的左端也过大，配上其他数仍然过大，所以令right--。若两端之和等于
k，直接取走这一对是安全的。假设某个最优方案把它们分别配给其他元素，那么这些配偶的数值分别等于另一端的数值，把原来的两对改为“两端一对、另外两个配偶一对”，配对数量不变。若只有一端原本被配对，让另一端替换它的原配偶也不减少数量；若两端都未使用，还能额外加上这一对，不可能比最优更差。因此总存在一个最优方案包含当前命中的两端，答案加一后将两个指针同时内移即可。相等数值也按两个不同下标处理，严格的
left < right保证最后只剩一个位置时不会让它自配对。每步都排除一个不能配对的元素，或取走一对可以属于最优解的元素，剩余区间不断缩小，循环结束时便得到最多操作次数。
解题步骤
- 将数组升序排序，初始化左右边界和答案。
- 当
left < right时，计算两端之和。- 和等于
k，答案加一并同时移动两个指针，表示两个元素均已消耗。- 和小于
k只右移左端，和大于k只左移右端。- 剩余不足两个元素时结束，返回配对次数。
代码实现
class Solution {
public int maxOperations(int[] nums, int k) {
// 排序后才有「左端最小、右端最大」的单调性
Arrays.sort(nums);
int left = 0;
int right = nums.length - 1;
int ans = 0;
// 严格小于：剩一个元素配不成对
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == k) {
// 两个元素一起被移除，所以两个指针都要内移
ans++;
left++;
right--;
} else if (sum < k) {
// 左端配上最大值都嫌小，它永远配不出 k，丢弃
left++;
} else {
// 右端配上最小值都嫌大，它永远配不出 k，丢弃
right--;
}
}
return ans;
}
}
import (
"sort"
)
func maxOperations(nums []int, k int) int {
// 排序后才有「左端最小、右端最大」的单调性
sort.Ints(nums)
left, right, ans := 0, len(nums)-1, 0
// 严格小于：剩一个元素配不成对
for left < right {
sum := nums[left] + nums[right]
if sum == k {
// 两个元素一起被移除，所以两个指针都要内移
ans++
left++
right--
} else if sum < k {
// 左端配上最大值都嫌小，它永远配不出 k，丢弃
left++
} else {
// 右端配上最小值都嫌大，它永远配不出 k，丢弃
right--
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n\log n)$，主要来自排序；双指针总共只移动线性次数。
- 空间复杂度：双指针扫描为 $O(1)$，排序空间依赖库实现。Go 的排序递归栈为 $O(\log n)$；Java 的排序合并路径可能申请 $O(n)$ 临时数组，保守按 $O(n)$ 计，不能只根据“双轴快排”名称认定它只有递归栈。实现依据见 Go 排序源码 和 OpenJDK 排序源码。
关键点总结
[!green]
- 排序后的极值关系决定哪一个端点可以安全排除，指针移动不能反向。
- 命中时的交换论证保证立即取走两端不会减少最优配对数量。
- 每次配对都消耗两个位置，两个指针必须同时推进。
解法对比：
哈希方法不修改输入，期望线性时间，但需要计数表。排序方法会修改数组，后续扫描仅用常量空间，整体额外空间仍需计入排序实现；如果必须保留输入，复制数组又会增加线性空间。两种方法都利用补数唯一，只是分别通过可用计数和有序端点排除完成配对。
易错点总结
[!yellow]
- 哈希配对成功后不减少补数计数，会让同一个旧元素被后面的多个元素重复使用。
- 先登记当前元素再查询，会在补数等于自身时查到当前元素，违反两个不同位置的要求。
- 只检查哈希键是否存在，可能把已经归零的计数当成仍有可用元素；应检查大于零。
- 用集合代替计数，会丢失同值元素的不同副本，低估可配对数量。
- 双指针没有先排序，端点不是剩余范围的极值，排除依据不成立。
- 命中后只移动一侧，会重复使用另一侧元素；循环使用小于等于则可能让单个位置与自己配对。
- 返回移除元素数而非配对数，会把题目要求的操作次数扩大一倍。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1. 两数之和 | 简单 | 同样查询互补值，本题需要持续消耗已匹配元素，最大化不重叠数对数量。 |
| 面试题 16.24. 数对和 | 中等 | 配对约束相同，原题输出所有数对，本题只返回最多能执行多少次配对。 |