LeetCode 1679. K 和数对的最大数目
目录
题目描述
题意分析
给定数组
nums和整数k，一次操作是从数组里挑出两个和为k的数并把它们移除，问最多能操作多少次。要返回的是操作次数，不是被移除的元素个数，这两个数差一倍，是最容易在最后一行写错的地方。「移除」这个动作决定了整道题的性质：元素一旦被用掉就不能再参与后续操作，所以每个下标最多出现在一个数对里。也就是说，题目要求的是把数组元素两两配对、且每对之和恰为
k的最大匹配数。如果把每个元素看成一个点、把每一对和为k的元素看成一条边，这就是一般图上的最大匹配，本身并不是一个能随手写出来的问题。但「和为定值」给这张图加了极强的结构：一个值为
x的元素只可能和值为k - x的元素连边，绝不可能和第三种值连边。于是整张图被劈成一堆互不相干的小块，每一块只涉及x与k - x两种取值，块与块之间不会互相抢元素。因此不需要真的跑匹配算法，只要在每个小块内部把能配的数量算对，再把各块的结果相加就是全局最优 —— 局部最优可以直接拼成全局最优，这正是允许我们用贪心 / 计数来做的根本原因。再看约束：
1 <= nums.length <= 10^5说明 $O(n)$ 与 $O(n \log n)$ 都能过，排序不是负担；1 <= nums[i] <= 10^9与1 <= k <= 10^9说明值域极大、不能开桶数组计数，只能用哈希表或者排序，而且两数之和最大2 * 10^9，虽然逼近 32 位上限但仍在int范围内，不必额外处理。另外元素全为正数，所以k - x若不在[1, 10^9]内直接就是无解，不会有负数搅局。最需要警惕的边界是
k为偶数、且数组里存在多个k / 2的情形：此时x与k - x是同一种值，配对发生在同一个值的内部。这时m个k / 2只能凑出m / 2对（向下取整），而不是m对 —— 任何把x和k - x当成两个独立集合来取min的写法都会在这里翻车。此外还有两类平凡边界：数组长度为1时一次操作都做不了，必须返回0；完全没有任何一对和为k时也返回0。
解法一：哈希表边遍历边配对
核心思路
既然值域大到没法开桶，就用哈希表记录「已经出现、但目前还没找到搭子」的元素及其个数。整个过程只扫一遍数组：拿到当前元素
x，先算出它需要的补数want = k - x，如果哈希表里还有等待中的want，就当场把这两个元素配成一对、把want的计数减一、答案加一；否则说明x暂时无人可配，把它自己放进哈希表里等后来者。关键在于「边遍历边消耗」而不是「先统计完再配对」。哈希表里存的从来不是「某个值出现了多少次」，而是「某个值还剩多少个可用」。一旦某个元素被配走，它的计数立刻减一，之后不会再被任何人看见，因此同一个元素物理上不可能被用两次。也正因为哈希表里只装「已经扫过的元素」，当前元素
x在被查询时还没有被记账，它绝不可能查到自己 —— 这就自动解决了k为偶数时k / 2与自身配对的陷阱：两个k / 2必须是先后出现的两个不同下标，才会被配成一对。那配对的顺序会不会影响最优性？不会。回到题意分析里的结论：能和
x配对的只有k - x，所以整个问题被拆成一堆独立的小块。在只涉及x与k - x（且2x != k）的块里，两种值的元素彼此完全等价 —— 谁配谁没有区别，答案恒为两者个数的较小值，而「见到一个能配的就配」恰好会一直配到较少的那一方用尽。在2x == k的块里，所有元素同值、也完全等价，「攒够两个就消掉一对」得到的就是m / 2。既然每一步的选择都在等价元素之间进行，就没有任何一步会让后面变差，贪心即最优。不变量：扫完前
i个元素时，ans是这前i个元素能凑出的最大操作次数，且哈希表中每个键的计数之和恰好等于i - 2 * ans（即所有还没被配走的元素个数），每个键的计数都非负。
解题步骤
- 建一个哈希表
need，语义固定为「值 → 还剩几个该值的元素在等待配对」。为什么不用「出现次数」：因为配对要消耗元素，只有「剩余可用数」这个语义才能让减一操作有意义。- 答案
ans初始化为0。- 从左到右遍历每个元素
x，计算它需要的补数want = k - x。为什么只需要看一个补数：和为定值意味着x的搭子取值唯一。- 若
need[want] > 0，说明前面有个还没配上的want正好在等着：把need[want]减一表示消耗掉它，ans加一。为什么必须判「计数大于0」而不是「键存在」：某个键的计数可能已经被减到0，键还在但人已经没了。- 否则把
need[x]加一，让x进入等待池。为什么这一步要放在else分支里：如果无条件先记账再查询，x就会在2x == k时查到刚记进去的自己，一个元素被当成两个用。- 遍历结束返回
ans。为什么不用管等待池里的残余：留在池子里的元素都是找不到搭子的，对答案没有贡献。以
nums = [3,1,3,4,3]、k = 6走一遍（这一组里k是偶数且k / 2 = 3出现了三次，正是自配对用例）：
- 初始：
need = {}，ans = 0。x = 3，want = 3，need[3] = 0配不上 → 记账，need = {3:1}，ans = 0。注意此刻查询发生在记账之前，所以这个3没有配到自己。x = 1，want = 5，need[5] = 0配不上 → 记账，need = {3:1, 1:1}，ans = 0。x = 3，want = 3，need[3] = 1 > 0配上了 →need = {3:0, 1:1}，ans = 1。消耗的是第一个3，两个下标不同。x = 4，want = 2，need[2] = 0配不上 → 记账，need = {3:0, 1:1, 4:1}，ans = 1。x = 3，want = 3，need[3] = 0配不上 → 记账，need = {3:1, 1:1, 4:1}，ans = 1。三个3只能凑出一对，第三个只能落单。- 返回
ans = 1，与官方样例一致。
代码实现
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(1)$。
- 空间复杂度：$O(n)$。最坏情况下没有任何一对能配上（例如所有元素互不相同且都找不到补数），哈希表会装下全部
n个元素。
关键点总结
- 哈希表里存的是「剩余可用数」而不是「出现次数」，语义一旦定死，减一操作才有意义，代码也不会在两种解释之间摇摆。
- 「边遍历边消耗」把「不重复使用同一元素」这件事变成了结构性保证，而不是靠额外判断去打补丁 —— 用掉就减掉，减掉就再也看不见。
- 先查询、后记账是这份代码最要紧的一行顺序。它同时解决了自配对陷阱和元素自己配自己的陷阱，颠倒过来就会在
2x == k时多算。- 判断条件写「计数大于
0」而不是「键存在」，因为计数减到0后键仍然留在表里，这是哈希计数类题目的通用坑。- 「和为定值」把配对图切成互不相干的小块，块内元素完全等价，这是贪心正确性的来源。以后遇到「和 / 差为定值的配对」类问题都可以先找这个结构。
- 面试视角：这份写法只有八行、一次遍历、没有第二个循环，是白板上最不容易写错的版本。写完主动补一句「查询放在记账之前，所以
k为偶数时两个k / 2必须来自不同下标」，等于替面试官把最想追问的边界先答了。
解法二：排序后双指针对撞
核心思路
换一个角度：如果数组是有序的，那么「和为
k」这件事就有了单调性 —— 固定左端往右走，和只会变大；固定右端往左走，和只会变小。于是可以让left从最小值出发、right从最大值出发向中间对撞，用当前和与k的大小关系来决定移动哪一侧，命中就把两个元素一起消掉。为什么这样贪心是对的？关键是两端必须配对，否则谁都配不上这个交换论证。考察当前区间
[left, right]：
- 若
nums[left] + nums[right] < k，那么nums[left]加上区间内任何元素都不超过这个和（因为nums[right]已经是区间最大值），所以nums[left]在这个区间里永远配不出k，可以永久丢弃、left右移。- 若
nums[left] + nums[right] > k，同理nums[right]加上区间内任何元素都不小于这个和（nums[left]是区间最小值），nums[right]也永远配不出k，丢弃、right左移。- 若
nums[left] + nums[right] == k，则把这两个配成一对不会让答案变差。设某个最优方案里nums[left]配的是b、nums[right]配的是a（a、b都在区间内），因为和都等于k，有nums[left] + b = k = nums[left] + nums[right]，故b的值等于nums[right]的值；同理a的值等于nums[left]的值。把这两对换成(nums[left], nums[right])与(a, b)，对数不变、和依然都是k，所以存在一个同样最优的方案包含这一对。若最优方案里只有其中一个被配走、另一个落单，直接让落单的那个替换掉搭子即可，对数也不变。因此总存在一个最优解在left与right相等于k时把它俩配在一起，贪心地取走它是安全的。这三条合起来说明：每一步要么删掉一个不可能配对的元素，要么取走一对可以出现在某个最优解里的元素，所以循环结束时累计的对数就是最大值。
不变量：
ans是区间[left, right]之外的元素已经贡献的最大操作次数，且区间外的元素要么已被配对消耗、要么已被证明在剩余元素中无法配出k；同时nums[left]与nums[right]始终是当前区间的最小值与最大值。
解题步骤
- 先把
nums升序排序。为什么必须排序：整套判断完全依赖「nums[left]是区间最小、nums[right]是区间最大」，无序数组里这两个前提都不成立。- 令
left = 0、right = nums.length - 1、ans = 0。- 当
left < right时循环。为什么是严格小于：left == right表示只剩一个元素，一个元素不能自己配自己凑成一对。- 计算
sum = nums[left] + nums[right]。- 若
sum == k：ans加一，同时left++与right--。为什么两个指针都要动：这一对里的两个元素都被移除了，只动一个等于把另一个留下来重复使用。- 若
sum < k：left++。为什么丢的是左边：nums[left]已经配上了区间里最大的数还嫌小，它在这个区间里没救了。- 若
sum > k：right--。为什么丢的是右边：nums[right]已经配上了区间里最小的数还嫌大，同理无解。- 循环结束返回
ans。以
nums = [1,3,4,5,5,6,9,9]、k = 10走一遍（排序后即为它本身，含5 + 5 = 10的自配对，且三个分支都会走到）：
left = 0（值1），right = 7（值9），sum = 10 == k→ans = 1，两个指针同时内移到left = 1、right = 6。left = 1（值3），right = 6（值9），sum = 12 > k→right左移到5。这个9被丢弃是对的：区间里最小的3都配它超了。left = 1（值3），right = 5（值6），sum = 9 < k→left右移到2。这个3被丢弃也是对的：区间里最大的6都配它不够。left = 2（值4），right = 5（值6），sum = 10 == k→ans = 2，left = 3、right = 4。left = 3（值5），right = 4（值5），sum = 10 == k→ans = 3，left = 4、right = 3。两个5是不同下标，合法自配对；注意此处指针交叉，left < right不再成立。- 循环结束，返回
ans = 3。对应的三对是(1,9)、(4,6)、(5,5)，与暴力枚举最大匹配的结果一致。
代码实现
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;
}
}
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)$。瓶颈完全在排序上；对撞过程中
left只增、right只减，两者一共移动不超过n步，这部分是 $O(n)$。- 空间复杂度：$O(\log n)$。只用了几个下标变量，额外开销来自排序的递归栈（Java 的
Arrays.sort对基本类型是双轴快排，Go 的sort.Ints是 pdqsort）；若输入本身有序、不需要排序，则为 $O(1)$。
关键点总结
- 排序的价值在于制造单调性：让「区间左端是最小值、右端是最大值」成立，从而能用一次比较就永久排除一个元素，把 $O(n^2)$ 的配对枚举压成一次线性扫描。
- 双指针贪心的正确性靠交换论证支撑，而不是靠「看起来对」。落笔前先想清楚「不动它会不会更好」，能不能构造出一个同样最优的方案包含当前选择。
- 命中后两个指针都要移动，这是「配对消耗两个元素」这一题意的直接翻译。指针移动次数应当和被移除的元素个数对齐。
- 排序 + 双指针的额外空间只有 $O(1)$（不计排序栈），当题目卡内存、或者输入已经保证有序时，它比哈希更划算。
- 面试视角：面试官问完哈希解法几乎必然追问「不用额外空间能做吗」，此时给出这一版就是标准答卷。讲的时候一定要把交换论证说出口 —— 双指针题的区分度往往不在能不能写出代码，而在能不能证明贪心不漏解。
解法对比
两种解法都能通过本题，取舍点在于时间与空间谁更紧，以及输入是否已经有序。
哈希解法胜在时间：一次遍历、不需要任何预处理，是本题的渐进最优时间。代价是要开一张最坏能装下全部元素的哈希表，而且哈希的常数不小 —— 在
10^5这个规模上，装箱后的Integer键与哈希冲突带来的开销，实测常常不比先排序再扫一遍快多少。它的另一个优势是只需要一遍流式访问，如果数据是从流里读进来、无法回头或不允许改动原数组，哈希是唯一可行的那个。双指针解法胜在空间：除了排序自身的递归栈之外不占额外内存，也没有哈希的常数问题，代码更短、分支更直白，白板上手写不易出错。代价是必须能够修改（或复制）输入数组，并且要付出排序的代价。但如果题目保证输入已经有序，排序这一步直接省掉，它就退化成纯粹的一次对撞扫描 —— 此时它在时间上与哈希持平、在空间上完胜，是无争议的更优解。
面试里的标准答法是两个都讲，并且讲清楚触发条件：先给哈希版作为主解，说明它一次遍历就能出答案；再主动补一句「如果面试官在意额外空间，或者输入已经有序，我会改成排序加双指针」，并顺手点出双指针需要写入原数组这个副作用。如果面试官进一步限制「不许改动原数组且不许开额外空间」，就要老实说明这两个条件同时成立时排序方案也失效了，此时只能退回哈希 —— 能识别出约束之间的冲突，比硬凑一个方案更能加分。
至于本题的语义边界，两种解法都要在同一个地方小心：
k为偶数时k / 2的自配对。哈希靠「先查询后记账」自动规避，双指针靠「命中后两指针同时内移」自动规避，机制不同但都必须写对。
易错点总结
- 先统计完出现次数再遍历配对，对
2x == k的值没有除以2：用[2,2,2,2], k = 4触发 → 四个2被当成「四个可配的元素」，返回4；用[3,1,3,4,3], k = 6触发 → 三个3全被计入，返回3，而正确答案分别是2和1。这正是应当改用「边遍历边配对」一次遍历写法的理由。- 双指针命中后只移动一个指针（
sum == k时只写了left++）：用[2,2,2,2], k = 4触发 →right始终停在末尾那个2上被反复使用，返回3而不是2。注意用[1,2,3,4], k = 5是测不出来的，它照样返回2，必须用含重复值的用例。- 哈希配对成功后忘记把补数计数减一：用
[3,1,3,4,3], k = 6触发 → 第一个3被后面两个3各配一次，返回2而不是1；用[2,2,2,2], k = 4触发 → 返回3而不是2。- 用
containsKey/map[want] != 0之外的存在性判断代替「计数大于0」：用[1,4,4], k = 5触发 →1的计数已被减到0，键还留在表里，于是第二个4又「配」了一次已经消失的1，返回2而不是1。- 用
Set代替计数哈希表：用[1,1,4,4], k = 5触发 → 第二个1被Set去重后丢失，只剩一次配对机会，返回1而不是2。本题元素可以重复，必须计数而非去重。- 哈希先把
x记进表再查补数：用[3,1,3,4,3], k = 6触发 → 第一个3刚记进表就查到「表里有个3」，自己和自己配成一对，返回2而不是1。查询与记账的先后顺序不能颠倒。- 双指针循环条件写成
left <= right：用[5], k = 10触发 → 唯一的元素自己和自己相加等于k，返回1而不是0；用[2,2,2], k = 4触发 → 返回2而不是1。- 双指针忘记先排序：用
[4,1,2,3], k = 5触发 → 首轮4 + 3 = 7 > 5就把3丢了，之后再也凑不出第二对，返回1而不是2。- 双指针的移动方向写反（
sum < k时移动right）：用[1,3,4,5,6,9], k = 10触发 → 和偏小时反而去砍最大值，越走越小，返回1而不是2。- 返回被移除的元素个数而不是操作次数：用
[1,2,3,4], k = 5触发 → 返回4而不是2。收尾时对一眼返回值语义，别让整题的正确逻辑倒在最后一行。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 面试题 16.24. 数对和 | 中等 | 同为最大匹配，但要返回数对本身而非个数，需在配对时记录具体元素 |
| 1. 两数之和 | 简单 | 只找一对且返回下标，元素不被消耗，哈希存的是下标而不是剩余可用数 |
| 167. 两数之和 II - 输入有序数组 | 中等 | 输入已有序可直接对撞省去排序，但命中即返回，不需要继续统计对数 |
| 15. 三数之和 | 中等 | 从两数扩展到三数，外层枚举加内层对撞，重点变成跳过重复值去重 |