K 和数对的最大数目 图解题解
这道题到底在问什么
- 输入
- nums=[1,2,3,4], k=5
- 输出
- 2（1+4、2+3）
- 输入
- nums=[3,1,3,4,3], k=6
- 输出
- 1（只能配出一对 3+3）
先想最直接的笨办法
一趟扫完，绿色这些是配成功的，一共 4 对，就是最多操作次数，和开头说的一致。表里剩的那几个值没找到搭档、留在原地。靠「边扫边即时配对」，一遍线性就解决，没有两两暴力。（动画第 25 步）
最优解：一步一步想明白
- 3记住「算搭档 y=k−x → 表里有 y 就配掉、没有就存 x」，下面每帧都在套它。
- 4开局这排是原数组，右边「待配数量」表还空着。指针从左到右走，每个数要么和表里的搭档当场配掉，要么先存进表里等人来配。
- 5扫到下标 0 的 1。要凑成和 5，它的搭档得是 5 − 1 = 4。下一步去表里看 4 还有没有存货。
- 6表里没有 4，1 暂时配不上，就把它自己存进表里 count[1] = 1，留着等后面出现 4 时来配它。
- 7扫到下标 1 的 3。要凑成和 5，它的搭档得是 5 − 3 = 2。下一步去表里看 2 还有没有存货。
- 8表里没有 2，3 暂时配不上，就把它自己存进表里 count[3] = 1，留着等后面出现 2 时来配它。
- 9扫到下标 2 的 2。要凑成和 5，它的搭档得是 5 − 2 = 3。下一步去表里看 3 还有没有存货。
- 10表里有 3(下标 1 那个)!当场和 2 配成一对，和正好 3 + 2 = 5，把这个 3 从表里消耗掉，答案加到 1。
- 11扫到下标 3 的 3。要凑成和 5，它的搭档得是 5 − 3 = 2。下一步去表里看 2 还有没有存货。
- 12表里没有 2，3 暂时配不上，就把它自己存进表里 count[3] = 1，留着等后面出现 2 时来配它。
- 13扫到下标 4 的 4。要凑成和 5，它的搭档得是 5 − 4 = 1。下一步去表里看 1 还有没有存货。
- 14表里有 1(下标 0 那个)!当场和 4 配成一对，和正好 1 + 4 = 5，把这个 1 从表里消耗掉，答案加到 2。
- 15扫到下标 5 的 2。要凑成和 5，它的搭档得是 5 − 2 = 3。下一步去表里看 3 还有没有存货。
- 16表里有 3(下标 3 那个)!当场和 2 配成一对，和正好 3 + 2 = 5，把这个 3 从表里消耗掉，答案加到 3。
- 17扫到下标 6 的 4。要凑成和 5，它的搭档得是 5 − 4 = 1。下一步去表里看 1 还有没有存货。
- 18表里没有 1，4 暂时配不上，就把它自己存进表里 count[4] = 1，留着等后面出现 1 时来配它。
- 19扫到下标 7 的 5。要凑成和 5，它的搭档得是 5 − 5 = 0。下一步去表里看 0 还有没有存货。
- 20表里没有 0，5 暂时配不上，就把它自己存进表里 count[5] = 1，留着等后面出现 0 时来配它。
- 21扫到下标 8 的 1。要凑成和 5，它的搭档得是 5 − 1 = 4。下一步去表里看 4 还有没有存货。
- 22表里有 4(下标 6 那个)!当场和 1 配成一对，和正好 4 + 1 = 5，把这个 4 从表里消耗掉，答案加到 4。
- 23扫到下标 9 的 4。要凑成和 5，它的搭档得是 5 − 4 = 1。下一步去表里看 1 还有没有存货。
- 24表里没有 1，4 暂时配不上，就把它自己存进表里 count[4] = 1，留着等后面出现 1 时来配它。
- 25一趟扫完，绿色这些是配成功的，一共 4 对，就是最多操作次数，和开头说的一致。表里剩的那几个值没找到搭档、留在原地。靠「边扫边即时配对」，一遍线性就解决，没有两两暴力。
⚠️ 容易写错的地方
✗ 错：先把所有数全存表再统一配
✓ 对：边扫边配:先查 y、能配就立刻配掉
即时配对天然保证每个数只用一次、不会重复配
✗ 错：配对时不看 count[y] > 0
✓ 对：必须确认 y 还有存货才配
count[y] = 0 时表里其实没货,硬配会多算
✗ 错：x 和 y 相等时(k = 2x)算错
✓ 对：靠计数:存一个 x 等下一个 x 来配
两个相同的 x 各占一次计数,第二个来时正好把第一个配掉
完整代码（Python / C++ / Java）
Python
from typing import List
from collections import Counter
class Solution:
def maxOperations(self, nums: List[int], k: int) -> int:
count = Counter()
ans = 0
for x in nums:
y = k - x
if count[y] > 0:
count[y] -= 1
ans += 1
else:
count[x] += 1
return ansC++
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
int maxOperations(vector<int>& nums, int k) {
unordered_map<int,int> count;
int ans = 0;
for (int x : nums) {
int y = k - x;
if (count[y] > 0) { count[y]--; ans++; }
else count[x]++;
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int maxOperations(int[] nums, int k) {
Map<Integer, Integer> count = new HashMap<>();
int ans = 0;
for (int x : nums) {
int y = k - x;
if (count.getOrDefault(y, 0) > 0) {
count.put(y, count.get(y) - 1);
ans++;
} else count.put(x, count.getOrDefault(x, 0) + 1);
}
return ans;
}
}复杂度
时间
O(n)
只扫一遍数组,每个数查表、改表都是 O(1)
空间
O(n)
计数表最多存 n 个还没配上的值
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 K 和数对的最大数目 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题和「两数之和」有什么关系?+
内核都是「用哈希表找配对值」:两数之和找一对返回下标;本题是反复配对、求最多对数,而且每个数用掉就不能再用,所以边扫边即时配对、配掉就消耗计数。
还有别的解法吗?+
可以先排序,再用对撞双指针:左右两端和等于 k 就配一对、两端都内移,大于 k 右端内移,小于 k 左端内移。那是 O(n log n);哈希计数法一遍扫是 O(n),更快,但双指针更省空间、也直观。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 K 和数对的最大数目 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。