K和数对的最大数目：哈希表与双指针两种解法详解

要是你在力扣上刷过 Hot 100，大概率见过这道“K 和数对的最大数目”。它题目短、通过率高，看着人畜无害，但很多人第一次写的时候，要么超时，要么多算少算，甚至还会被“元素只能用一次”这个条件绕晕。今天我就把这道题彻底拆开讲透，从题意理解到两种主流解法，再到几个我实际调试中踩过的细节坑，一次性说清楚。

先说结论：这道题考的是哈希表计数，正规解法能做到 O(n)，排序加双指针也能解，但适合不同的场景。无论你是刚入门算法的小白，还是准备面试想快速过一遍经典题的老手，这篇都值得看完。我会把每一步背后的“为什么”也讲明白，而不是只给你一份能通过的代码。

1. 这道题到底在问什么：先读懂题意再动手

题目的大意是：给你一个整数数组 nums 和一个整数 k，每次操作可以挑选两个数，让它们的和等于 k，然后从数组里移除这两个数。问最多能执行多少次这样的操作。

我第一次刷的时候差点理解偏了，以为是要找到所有和等于 k 的“数对组合”，然后去重。其实题目强调的是：每个数组元素只能用一次，而且我们只关心“最多能配对多少次”，不关心具体是哪几对、也不要求输出配对方案。

举个最简单的例子：nums = [1, 2, 3, 4]，k = 5。能配成的对子是 [1,4] 和 [2,3]，结果是 2。如果把数组换成 [1, 2, 3, 4, 5]，k = 5，能配成 2 对，比如 [1,4] 和 [2,3]，剩下 5 没法配对，因为 5 需要再找一个 0，但数组里没有 0。如果数组是 [3, 3, 3, 3]，k = 6，最多能配 2 对，也就是两两组合。

这道题之所以被归类到哈希表专题，是因为“找配对”这件事本质上是：遍历到当前元素 num 时，去查一下之前有没有出现过 k - num。如果有，就用掉一个；如果没有，就把当前元素存起来，等后面的兄弟来找它。

我在给同事讲这道题的时候常用一个生活化类比：相当于你在组织舞会，每个人手里拿一个号码牌，两个人号码相加等于 k 才能配对进场。你在门口一个一个放人进来，每进来一个新人，就先看看场内有没有人号码是 k - 新人号码，有就拉走一对，没有就让他进场等着。最终配成的对数就是答案。这个类比能帮你理解“一边遍历一边配对”的核心逻辑，我们在第 2 节详细展开。

2. 从暴力到 O(n)：两种主流解法拆解

2.1 先看一眼暴力搜索为什么不行

最直觉的做法是两层循环枚举所有数对，判断两数之和是否等于 k，配对成功后把两个数标记为“已使用”。这个方案的时间复杂度是 O(n^2)，在 nums 长度达到 10^5 量级时会直接超时。你在力扣上提交，基本会给你一个 TLE（Time Limit Exceeded）。

暴力解法还有一个隐藏问题：标记“已使用”需要额外数组，或者需要把元素临时从数组里“删除”。如果用 List 真的删除，删除操作本身是 O(n) 的，整体复杂度会更高。所以暴力只能用来在小规模数据上验证答案，不能作为正式提交方案。

2.2 哈希表一边遍历一边配对：最优解的核心思路

哈希表解法的思路非常干净：用一个 Map 统计“当前还没配对的数字”及其出现次数。遍历数组，对每个元素 num，先计算 target = k - num，去 Map 里查 target 的计数：

• 如果 target 存在且计数大于 0，说明当前元素可以和之前某个元素配对，操作数加 1，同时把 target 的计数减 1。
• 如果 target 不存在或计数已经是 0，说明当前元素暂时没有舞伴，把它放进 Map，计数加 1。

这里有一个关键点：为什么这种“贪心配对”能得到全局最优解？你可以这样想：当前元素如果恰好能和前面的某个元素配对，那么现在配掉一定不比留到以后更差。因为后面的元素不会依赖当前这个元素去配对，当前元素留得越久反而越可能占用 Map 空间。简单说，有机会配对就立刻配，这是这个场景下的最优策略。

这个解法的时间复杂度是 O(n)，每个元素最多进 Map 一次、出 Map 一次；空间复杂度是 O(n)，最坏情况下所有元素都配不上对，全部躺在 Map 里。

2.3 排序加双指针：换一种思维也能 O(n log n)

另一种经典思路是排序后使用左右双指针。先把数组排序，然后 left 指向最小元素，right 指向最大元素。如果 nums[left] + nums[right] 正好等于 k，说明找到一对，操作数加 1，然后 left 右移、right 左移；如果两数之和小于 k，说明左边的太小了，left 右移；如果大于 k，说明右边的太大了，right 左移。

这里的正确性依赖有序性：排序之后，左边指针只能让和变大，右边指针只能让和变小，所以不会漏掉任何可能的配对。这个思路的代码非常短，逻辑也更直观，我看到很多同学面试时反而更愿意写双指针版本，因为不用费劲解释“计数减一”的过程。

复杂度上，排序最快是 O(n log n)，双指针扫描本身是 O(n)，所以整体是 O(n log n)。空间复杂度取决于排序实现，Java 对 int[] 的 Arrays.sort() 是双轴快排，额外空间可以认为是 O(log n)，不算大。

两种解法对比我整理成了表格，方便你根据场景取舍：

我的个人建议是：两种解法都要会写。因为面试官可能会追问“如果内存特别紧张怎么办”，这时候双指针就是更好的答案；但如果面试官想考你哈希表，那你必须先给出 O(n) 的解法。两者互相补充，不是替代关系。

3. 哈希表解法的四个关键细节，绕过所有坑

3.1 为什么一边遍历一边配对不会重复使用元素

这是我自己第一次写这道题时最困惑的地方，也是面试时考官最爱追问的点。

核心在于：数组里的元素只会被访问一次，而配对发生的时候，是“当前元素”和“Map 里已有的某个元素”在配对。当前元素配对成功后被使用掉了，Map 里的那个目标元素计数减一后也被使用掉了。由于我们从头到尾只遍历一次数组，每个元素只有一次机会参与配对，不存在一个元素同时跟多个元素配对的可能性。

举个例子：nums = [1, 2, 3, 4]，k = 5。

• 遍历到 1：target 是 4，Map 里没有 4，把 1 放进 Map。
• 遍历到 2：target 是 3，Map 里没有 3，把 2 放进 Map。
• 遍历到 3：target 是 2，Map 里有 2，计数减一，操作数变成 1。
• 遍历到 4：target 是 1，Map 里有 1，计数减一，操作数变成 2。

整个过程，1、2、3、4 都被使用了一次，没有重复，答案恰好是 2。

如果你采用“先统计所有元素频率，再统一配对”的思路，反而容易踩坑，下一小节专门讲这个。

3.2 先统计再配对的误区：为什么要除以 2

我看到很多题解、包括一些新手写的代码，会先遍历一遍数组，把每个数字出现的次数存进 Map，然后再次遍历 Map 的 key，对于每个 key，去配对 k - key，取两边的较小次数加到答案里。这个思路本身是对的，但它有一个巨大的坑：一对数字会被算两次。

假设 key 和 target 都存在于 Map 中，当你遍历到 key 的时候，你会用 min(freq[key], freq[target]) 加一次；当你遍历到 target 的时候，又会对 key 再做一次一模一样的操作。如果不加任何限制，答案会翻倍。

常见的处理方式有两种。第一种是最终答案除以 2；第二种是遍历 Map 时只处理 key < target 的情况，这样每个配对只会被计算一次。不过还有一种更隐蔽的情况：如果 key 恰好等于 target，也就是 k 是偶数且存在 k/2 这个元素，此时配对数量不是 min 再除以 2，而是 freq[key] / 2。

正因为这个“先统计再配对”要考虑的边界太多，我推荐你优先掌握“一边遍历一边配对”的写法，它在逻辑上天然规避了上面所有问题，代码也更短，提交后更不容易出错。如果面试官要求你展示两种写法，你可以讲清楚两种思路的差异和先统计版的坑，这反而是加分项。

3.3 特殊值 k/2 的处理逻辑

k/2 这种情况值得单独拿出来说，因为它是数值相等、相互之间才能配对的典型场景。比如 k = 6，数组里都是 3，那么只有两个 3 之间可以配对，三个 3 最多只能配成 1 对，四个 3 配成 2 对。

在一遍遍历法里，这个逻辑是自动实现的：第一个 3 进 Map；第二个 3 发现 target 是 3，Map 里计数为 1，配对成功，计数减到 0；第三个 3 发现 Map 里没有 3，只能进 Map；第四个 3 再配掉第三个。所以四个 3 得到 2 对，三个 3 得到 1 对，完全正确，不需要额外写代码判断。

但如果你用先统计再配对的方式，就必须显式判断 key == target 的情况，用 freq[key] / 2 而不是 freq[key]。很多初学者的错误就在这里，他们把 k/2 这种普通配对逻辑套用上去，然后发现结果不对。

3.4 负数与重复元素并不需要特殊处理

有人会担心，如果数组里有负数，或者某个数字出现非常多次，上面的算法会不会出问题？其实不会。哈希表存的是数字本身和出现次数，跟正负无关。你只需要保证 k - num 的计算没问题，Map 的 key 可以是任意整数。

重复元素多的场景同样安全，因为 Map 的 value 是计数，允许同一数字出现多次，配对时每次只减一。你可以把“计数”理解成“舞池里还有多少个拿同一个号码的人”，配对成功一个人，对应号码的人数就减一，不会出现负数次数。

我在本地测试过极端用例：nums = [0, 0, 0, 0, 0]，k = 0。所有元素都是 0，target 也是 0，走一遍逻辑：第一个 0 进 Map，第二个 0 配掉第一个，第三个 0 进 Map，第四个 0 配掉第三个，最后结果 2。手动验证一下，五个 0 里最多能配 2 对，完全正确。

4. 代码实现与复杂度分析：Java 和 Python 双版本

4.1 Java 版本：HashMap 计数法

class Solution { public int maxOperations(int[] nums, int k) { Map<Integer, Integer> freq = new HashMap<>(); int ans = 0; for (int num : nums) { int target = k - num; if (freq.getOrDefault(target, 0) > 0) { ans++; freq.put(target, freq.get(target) - 1); } else { freq.put(num, freq.getOrDefault(num, 0) + 1); } } return ans; } }

这里有个小细节：当 target == num 时，上面的代码仍然正确。因为你是先查 target 的计数，再决定放入还是减少，不会把刚放入的元素又拿出来配对。

如果你愿意用 getOrDefault，可以少写几个 if-else，但逻辑是一样的。注意 Java 的 HashMap 里 put 同一个 key 会覆盖旧值，所以 freq.put(target, freq.get(target) - 1) 等价于“把计数减一后放回去”。如果你的 Java 版本比较新，也可以考虑用 merge 方法一行实现累加，但可读性稍差。

4.2 Python 版本：字典计数法

class Solution: def maxOperations(self, nums: List[int], k: int) -> int: freq = {} ans = 0 for num in nums: target = k - num if freq.get(target, 0) > 0: freq[target] -= 1 ans += 1 else: freq[num] = freq.get(num, 0) + 1 return ans

Python 的 dict 在 key 不存在时调用 get 会返回默认值 0，所以整个逻辑非常清爽。也可以用 collections.Counter 预设所有计数，但那样就又回到“先统计再配对”的版本了，不推荐。

4.3 排序双指针版本（Java）

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) { left++; } else { right--; } } return ans; } }

双指针版本的边界条件是 left < right，因为配对一个元素必须有另一个不同下标的元素，二者不能是同一个。这里不需要担心 k/2 的情况，因为两个指针指向的是不同位置，即使值相同也代表两个不同元素。

4.4 手动跑通全流程：一次调试现场

为了验证代码正确性，我会在本地写一段 main 方法，手动粘几个测试用例，打印 ans。比如：

public class Main { public static void main(String[] args) { Solution solution = new Solution(); System.out.println(solution.maxOperations(new int[]{1, 2, 3, 4}, 5)); // 2 System.out.println(solution.maxOperations(new int[]{3, 1, 3, 4, 3}, 6)); // 1 System.out.println(solution.maxOperations(new int[]{3, 3, 3, 3}, 6)); // 2 System.out.println(solution.maxOperations(new int[]{0, 0, 0, 0, 0}, 0)); // 2 System.out.println(solution.maxOperations(new int[]{1}, 2)); // 0 System.out.println(solution.maxOperations(new int[]{}, 5)); // 0 } }

这组用例覆盖了普通配对、k/2 场景、全是相同元素、空数组、单个元素等常见边界。我实际调试中最容易翻车的场景是 k = 0 且数组全是 0：如果某个版本代码里用 freq.containsKey(target) 而不是判断计数大于 0，就会在“计数已经减到 0 后仍然命中”，导致重复配对。这也是为什么我坚持用“计数 > 0”作为配对条件。

5. 相似题目串讲：从两数之和到整个配对类题型

这道“K 和数对的最大数目”不是孤立题，它属于“配对类”题型的经典代表。我把这类题的前后脉络梳理一下，你按照这个顺序去刷，会比零散刷题效率高很多。

第一梯队的入门题是 LeetCode 1 两数之和：给定数组和一个 target，返回两个数的下标。它的核心思路就是一遍遍历哈希表，边遍历边查找 target - num。这道题和“K 和数对的最大数目”几乎同源，区别只在于两数之和要返回下标，所以 Map 里存的是“值 -> 下标”而不是“值 -> 计数”。

第二梯队是 LeetCode 167 两数之和 II：输入数组已经有序，要求你尽量少用额外空间。最优解就是双指针，代码和上面第 4.3 节几乎一样。你一旦掌握了有序数组的双指针思想，167 和这道 K 数对题目可以一起过。

第三梯队是 LeetCode 15 三数之和：排序后固定第一个数，剩下的两个数用双指针。它考察的是去重技巧和指针移动时机，比配对题难一截。但你会发现，三数之和内部的那个“找两数之和”的操作，本质就是我们这里说的双指针配对。

第四梯队是 LeetCode 454 四数相加 II：给你四个数组，从每个数组各取一个数，让四数之和为 0，统计可能组合数。解法是两两分组，先用哈希表存前两个数组的和频次，再遍历后两个数组查负和。这是“哈希表分组统计”的经典应用，思路和“K 数对”一脉相承。

我建议你刷完“K 和数对的最大数目”后，立刻刷 1、167，再考虑 15 和 454。这样一条线下来，哈希表配对和双指针配对这两大武器就都上手了。刷题最忌讳的就是孤立地背题解，把这些题目串成一条“配对题”专题，你会发现核心模板就那么几个。

有一个通用模板值得背下来：当你需要在一组数据中寻找“互补元素”时，优先考虑用哈希表记录“之前见过什么”；当数据有序时，优先考虑双指针。这两个思路能解决 80% 的数组配对问题。

6. 常见问题与调试技巧实录

我在带新人刷题、以及自己反复提交这道题的过程中，整理了几个高频问题，做成表格供你快速排查：

除了表格里的问题，我再补充几条我自己的经验：

第一，提交前一定要验证 k 为负数、数组元素为负数的情况。虽然 LeetCode 原题通常限制在正数范围内，但面试官有时会临时改条件。哈希表法天然支持负数，但有些肉眼可见的小 bug 会在负数场景下暴露，比如用 target = k - num 时如果整数溢出就会出问题。稳妥做法是使用 long 保存和值，避免边界溢出。

第二，关于整数溢出的讨论。原题的 nums[i] 和 k 都在 int 范围内，两个 int 相加可能超出 int 的范围。虽然力扣给的数据不会触发溢出，但为了严谨，我习惯在计算 sum = nums[left] + nums[right] 时用 long 接收，或者在哈希表版本里用 long 计算 target。别小看这个习惯，面试官问“你觉得这段代码有什么隐患”的时候，你能说出溢出点，会加不少印象分。

第三，本地调试时我习惯用断言代替打印。比如在 Java 里直接 assert maxOperations(new int[]{1,2,3,4}, 5) == 2，跑一次就知道有没有回归问题。如果你用 IDE，直接写一个参数化的测试类也可以。刷题不要求写完整测试工程，但一个 main 方法里放六七个断言，能帮你快速验证边界场景。

第四，千万别忽略“排序会改变原数组”这件事。如果你在题目之外还需要原始数组的顺序，那么双指针方案会让事情变复杂。这时候哈希表版本就是更安全的选择。面试时如果考官追加一句“我不想修改原数组”，你要能立刻给出哈希表解法。

最后再分享一个刷题技巧：这道题我每次重新刷的时候，都会试试用不同语言写一遍，再改写成双指针版本。同一个逻辑用两种语言、两种思路各写一遍，记忆会非常牢固。如果你时间有限，至少要把一边遍历哈希表的版本写到肌肉记忆的程度，因为它是这类题目最核心的模板。