LeetCode-Go 题解1679 Max Number of K-Sum Pairs——哈希计数配对移除的两种实现与源码剖析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文以开源仓库 LeetCode-Go 中 1679.Max-Number-of-K-Sum-Pairs 的题解文档 为核心完整还原题目定义与两套 Go 哈希计数实现并结合仓库内的源码与单元测试逐行拆解算法原理、边界处理与复杂度。读完你将掌握一类从数组中配对移除元素、求最大操作数问题的标准解法理解频次统计 半值特判与单趟在线配对两种哈希策略的差异并能在仓库中直接运行测试复现结果。题目与题意题目原题英文给定一个整数数组nums和一个整数k。每次操作中你可以从数组中选出两个和等于k的整数并将它们从数组中移除。返回你可以在数组上执行的最大操作数。示例 1Input: nums [1,2,3,4], k 5 Output: 2 Explanation: Starting with nums [1,2,3,4]: - Remove numbers 1 and 4, then nums [2,3] - Remove numbers 2 and 3, then nums [] There are no more pairs that sum up to 5, hence a total of 2 operations.示例 2Input: nums [3,1,3,4,3], k 6 Output: 1 Explanation: Starting with nums [3,1,3,4,3]: - Remove the first two 3s, then nums [1,4,3] There are no more pairs that sum up to 6, hence a total of 1 operation.题目大意中文给你一个整数数组nums和一个整数k。每一步操作中你需要从数组中选出和为k的两个整数并将它们移出数组。返回你可以对数组执行的最大操作数。输入约束与规模分析原文档给出的约束如下1 nums.length 10^51 nums[i] 10^91 k 10^9注原文档中 105、109 是10^5、10^9的上标在 Markdown 渲染中丢失所致实际含义为10^5与10^9。这三个约束直接决定了算法选型数组长度可达10 万说明O(n²)的暴力双重循环不可行需要O(n)或O(n log n)的解法数值范围可达10 亿无法使用定长计数数组必须使用哈希表Go 中即map[int]int记录频次nums[i]与k均为正数且最大不超过10^9在 64 位平台下 Go 的int类型足以安全存储k - num的差值无溢出风险。思路起点这是 Two Sum 的加强版原文档的解题思路开门见山读完题第一感觉这道题是 TWO SUM 题目的加强版。与经典的 0001.Two-Sum 相比本题有两点本质差异不是找一组解而是找所有解需要统计数组中能配成和为k的最大数对数量每个元素至多被使用一次数组存在重复元素nums中同一数值可能出现多次如示例 2 中的三个3因此配对时必须以频次为单位计数而不能简单地记录某个值是否出现过。核心观察对于任意两个数a、b若a b k则b k - a。于是问题转化为统计nums中所有满足a b k且互不重复使用的(a, b)数对数量。利用 Two Sum 中经典的 map 做法可以在O(n)时间内解决。此外还有一个需要优先考虑的特殊情形两个数相同且都等于k / 2仅当k为偶数时成立。因为k/2 k/2 k这类元素可以两两配对单独处理能避免在通用逻辑中被漏算或重复计算。解法一频次统计 半值特判优化版这是仓库内标注为解法一 优化版的实现完整代码位于 1679. Max Number of K-Sum Pairs.gopackage leetcode // 解法一 优化版 func maxOperations(nums []int, k int) int { counter, res : make(map[int]int), 0 for _, n : range nums { counter[n] } if (k 1) 0 { res counter[k1] 1 // 能够由 2 个相同的数构成 k 的组合已经都排除出去了剩下的一个单独的也不能组成 k 了 // 所以这里要把它的频次置为 0 。如果这里不置为 0下面代码判断逻辑还需要考虑重复使用数字的情况 counter[k1] 0 } for num, freq : range counter { if num k/2 { remain : k - num if counter[remain] freq { res counter[remain] } else { res freq } } } return res }逐步拆解第一步统计频次。遍历一遍nums用map[int]int记录每个数值出现的次数。这一步的时间复杂度为O(n)。第二步处理半值特判仅当k为偶数。(k 1) 0判断k是否为偶数若为偶数则k1即k/2与自身配对即可凑成k。counter[k1] 1表示每 2 个k/2组成一对对频次整除 2 后累加到结果中。例如示例 2 中nums [3,1,3,4,3]、k 6counter[3] 3则3 1 1即最多可配成 1 对(3,3)剩余一个单独的3无法再参与任何配对。紧接着把counter[k1]置为 0这是本解法最精妙的一步。原文档注释解释得很清楚能够由 2 个相同的数构成k的组合已经全部排除出去了剩下的单个k/2也不可能再与别的数组成k因为唯一能和它配对的还是k/2本身因此将其频次清零防止后续循环中重复使用这些数字。之所以这样做是安全的还在于对任意num k/2的数值其补数remain k - num k/2永远不会等于k/2所以将counter[k/2]清零不会影响其他数对的统计。第三步遍历 map统计互补数对。num k/2这一条件是本解法的第二个关键点。它保证了每个无序数对只被统计一次若num k/2则remain k - num k/2 num此时只有遍历到较小的num时才会计数遍历到remain时因其大于k/2会被跳过若num k/2仅偶数k时存在此时counter[k/2]已在第二步被清零贡献为 0不会重复计算。对于每个满足条件的num其补数为remain k - num。可配成的对数取决于两者的频次较小值min(counter[remain], freq)——因为每配对一次需要同时消耗一个num和一个remain配对数量受限于较少的那一方。代码中通过if counter[remain] freq取较小者累加与min等价。以示例 1nums [1,2,3,4]、k 5为例k为奇数跳过特判遍历 map 时num 11 2配remain 4取min(1,1)1num 22 2配remain 3取min(1,1)1num 3、4均大于k/2被跳过。最终结果1 1 2与预期一致。解法二单趟在线配对原文档还提供了解法二思路是边遍历、边配对每读入一个数先登记频次再立刻检查它的补数是否已在之前的遍历中出现过。完整代码位于 1679. Max Number of K-Sum Pairs.gopackage leetcode // 解法二 func maxOperations_(nums []int, k int) int { counter, res : make(map[int]int), 0 for _, num : range nums { counter[num] remain : k - num if num remain { if counter[num] 2 { res counter[num] - 2 } } else { if counter[remain] 0 { res counter[remain]-- counter[num]-- } } } return res }逐步拆解分支一num remain即2 * num k。只有当k为偶数且当前数恰为k/2时才进入。此时需要两个相同的num才能配对因此检查counter[num] 2当前这个num刚被登记加上之前出现过的至少一个配对成功后counter[num] - 2消耗掉两个。分支二num ! remain一般情形。若补数remain在之前的遍历中出现过counter[remain] 0说明当前num可以与之前某个remain配对res记录一次操作counter[remain]--消耗一个历史补数counter[num]--则把刚登记的当前数撤销因为它已被配对使用。以示例 1nums [1,2,3,4]、k 5手动走一遍读入1counter[1] 1remain 4不存在不配对读入2counter[2] 1remain 3不存在不配对读入3counter[3] 1remain 2存在res 1counter[2] 0counter[3] 0读入4counter[4] 1remain 1存在res 2counter[1] 0counter[4] 0。最终res 2与示例 1 输出一致。值得注意的是解法二天然规避了同一数对重复计数的问题——因为配对总是发生在当前元素与更早出现的元素之间每个元素只会被消费一次无需像解法一那样依赖num k/2的手动去重。两种解法对比与复杂度分析维度解法一优化版解法二单趟配对遍历方式两趟先统计频次再遍历 map单趟边读边配对半值k/2处理特判分支 频次清零特判分支 双消耗去重策略num k/2保证每个数对只计一次在线配对天然不重复时间/空间复杂度O(n)/O(n)O(n)/O(n)两种实现的时间复杂度均为O(n)map 的均摊读写为O(1)空间复杂度均为O(n)频次表。解法一逻辑集中、易于推演正确性解法二流式处理、更贴近读一个、配一个的直觉且不需要在循环中额外维护半值清零。在数组规模达到10^5时两者都能在线性时间内完成均远优于暴力枚举的O(n²)。仓库测试用例与验证仓库为本题配备了完整的单元测试位于 1679. Max Number of K-Sum Pairs_test.go。测试采用了本仓库统一的question1679表驱动结构para1679封装输入参数nums与kans1679封装期望答案然后逐条断言maxOperations的输出。测试文件中共覆盖 4 个用例输入 numsk期望输出用例要点[1,2,3,4]52对应题目示例 1奇数k常规配对[3,1,3,4,3]62→1对应题目示例 2偶数k的半值配对[2,5,4,4,1,3,4,4,1,4,4,1,2,1,2,2,3,2,4,2]34大数组 奇数k考验去重逻辑4 对(1,2)[2,5,5,5,1,3,4,4,1,4,4,1,3,1,3,1,3,2,4,2]68偶数k全类型综合(3,3)2 对、(1,5)3 对、(2,4)3 对以最后一个用例验证解法一的半值处理counter[3] 44 1 2先计入 2 对(3,3)并清零随后num 1配5counter[5] 3计 3 对num 2配4counter[4] 5取min(5, 3) 3计 3 对总计2 3 3 8与期望输出一致。注意到测试循环中同时调用了maxOperations(p.nums, p.k)与maxOperations_(p.nums, p.k)即两个版本的实现都被实际执行验证且都会覆盖上述全部用例。在仓库中运行测试在仓库根目录执行题目目录名不含空格可直接作为路径参数go test -v -run Test_Problem1679 ./leetcode/1679.Max-Number-of-K-Sum-Pairs/-v会打印测试细节-run指定仅运行本题的Test_Problem1679测试函数。若需确认仓库全量题解均通过可运行 gotest.sh 脚本——它会对./leetcode/...下所有包一次性执行go test -covermodeatomic -coverprofilecoverage.txt生成单一合法的覆盖率文件仓库根目录的 coverage.txt 即其产物。本项目模块名为github.com/halfrost/LeetCode-GoGo 版本为 1.19见 go.mod。边界条件与易错点总结偶数k且存在k/2k/2只能与自身配对且配对后剩余单个k/2无法再与其他任何数配对。解法一通过频次整除 2 后清零处理解法二通过消耗两个counter[num]处理二者缺一不可否则会漏计或重复计数。数组元素可重复必须用频次而非布尔标记记录元素且每次配对都要消耗频次保证每个元素至多使用一次。数对去重(a, b)与(b, a)是同一个数对。解法一用num k/2约束遍历方向解法二因当前元素只与历史元素配对而天然避免。取频次较小值配对数量受限于min(counter[remain], freq)若直接取较大值会导致同一元素被重复使用。k为奇数不存在x x k的整数解半值特判分支自动跳过不影响正确性。完全没有可配对元素如nums中所有数之和都不等于kres保持 0两种实现均正确返回。小结本题是 Two Sum 家族中极具代表性的计数配对变体。LeetCode-Go 仓库中的两份 Go 实现分别展示了两种经典策略解法一统计频次后统一配对以num k/2与半值清零两个关键技巧保证每个数对恰好计数一次解法二单趟在线配对则利用流式处理的天然优势规避去重问题。二者时间复杂度均为O(n)配合仓库内 4 组覆盖偶数/奇数k、重复元素、大数组场景的单元测试读者可以快速验证算法正确性并将该频次哈希 补数查找模式迁移到其他配对类问题如三数之和的配对子问题、字符串字符配对统计等中。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode-Go 题解：1679 Max Number of K-Sum Pairs——哈希计数配对移除的两种实现与源码剖析
LeetCode-Go 题解1679 Max Number of K-Sum Pairs——哈希计数配对移除的两种实现与源码剖析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文以开源仓库 LeetCode-Go 中 1679.Max-Number-of-K-Sum-Pairs 的题解文档 为核心完整还原题目定义与两套 Go 哈希计数实现并结合仓库内的源码与单元测试逐行拆解算法原理、边界处理与复杂度。读完你将掌握一类从数组中配对移除元素、求最大操作数问题的标准解法理解频次统计 半值特判与单趟在线配对两种哈希策略的差异并能在仓库中直接运行测试复现结果。题目与题意题目原题英文给定一个整数数组nums和一个整数k。每次操作中你可以从数组中选出两个和等于k的整数并将它们从数组中移除。返回你可以在数组上执行的最大操作数。示例 1Input: nums [1,2,3,4], k 5 Output: 2 Explanation: Starting with nums [1,2,3,4]: - Remove numbers 1 and 4, then nums [2,3] - Remove numbers 2 and 3, then nums [] There are no more pairs that sum up to 5, hence a total of 2 operations.示例 2Input: nums [3,1,3,4,3], k 6 Output: 1 Explanation: Starting with nums [3,1,3,4,3]: - Remove the first two 3s, then nums [1,4,3] There are no more pairs that sum up to 6, hence a total of 1 operation.题目大意中文给你一个整数数组nums和一个整数k。每一步操作中你需要从数组中选出和为k的两个整数并将它们移出数组。返回你可以对数组执行的最大操作数。输入约束与规模分析原文档给出的约束如下1 nums.length 10^51 nums[i] 10^91 k 10^9注原文档中 105、109 是10^5、10^9的上标在 Markdown 渲染中丢失所致实际含义为10^5与10^9。这三个约束直接决定了算法选型数组长度可达10 万说明O(n²)的暴力双重循环不可行需要O(n)或O(n log n)的解法数值范围可达10 亿无法使用定长计数数组必须使用哈希表Go 中即map[int]int记录频次nums[i]与k均为正数且最大不超过10^9在 64 位平台下 Go 的int类型足以安全存储k - num的差值无溢出风险。思路起点这是 Two Sum 的加强版原文档的解题思路开门见山读完题第一感觉这道题是 TWO SUM 题目的加强版。与经典的 0001.Two-Sum 相比本题有两点本质差异不是找一组解而是找所有解需要统计数组中能配成和为k的最大数对数量每个元素至多被使用一次数组存在重复元素nums中同一数值可能出现多次如示例 2 中的三个3因此配对时必须以频次为单位计数而不能简单地记录某个值是否出现过。核心观察对于任意两个数a、b若a b k则b k - a。于是问题转化为统计nums中所有满足a b k且互不重复使用的(a, b)数对数量。利用 Two Sum 中经典的 map 做法可以在O(n)时间内解决。此外还有一个需要优先考虑的特殊情形两个数相同且都等于k / 2仅当k为偶数时成立。因为k/2 k/2 k这类元素可以两两配对单独处理能避免在通用逻辑中被漏算或重复计算。解法一频次统计 半值特判优化版这是仓库内标注为解法一 优化版的实现完整代码位于 1679. Max Number of K-Sum Pairs.gopackage leetcode // 解法一 优化版 func maxOperations(nums []int, k int) int { counter, res : make(map[int]int), 0 for _, n : range nums { counter[n] } if (k 1) 0 { res counter[k1] 1 // 能够由 2 个相同的数构成 k 的组合已经都排除出去了剩下的一个单独的也不能组成 k 了 // 所以这里要把它的频次置为 0 。如果这里不置为 0下面代码判断逻辑还需要考虑重复使用数字的情况 counter[k1] 0 } for num, freq : range counter { if num k/2 { remain : k - num if counter[remain] freq { res counter[remain] } else { res freq } } } return res }逐步拆解第一步统计频次。遍历一遍nums用map[int]int记录每个数值出现的次数。这一步的时间复杂度为O(n)。第二步处理半值特判仅当k为偶数。(k 1) 0判断k是否为偶数若为偶数则k1即k/2与自身配对即可凑成k。counter[k1] 1表示每 2 个k/2组成一对对频次整除 2 后累加到结果中。例如示例 2 中nums [3,1,3,4,3]、k 6counter[3] 3则3 1 1即最多可配成 1 对(3,3)剩余一个单独的3无法再参与任何配对。紧接着把counter[k1]置为 0这是本解法最精妙的一步。原文档注释解释得很清楚能够由 2 个相同的数构成k的组合已经全部排除出去了剩下的单个k/2也不可能再与别的数组成k因为唯一能和它配对的还是k/2本身因此将其频次清零防止后续循环中重复使用这些数字。之所以这样做是安全的还在于对任意num k/2的数值其补数remain k - num k/2永远不会等于k/2所以将counter[k/2]清零不会影响其他数对的统计。第三步遍历 map统计互补数对。num k/2这一条件是本解法的第二个关键点。它保证了每个无序数对只被统计一次若num k/2则remain k - num k/2 num此时只有遍历到较小的num时才会计数遍历到remain时因其大于k/2会被跳过若num k/2仅偶数k时存在此时counter[k/2]已在第二步被清零贡献为 0不会重复计算。对于每个满足条件的num其补数为remain k - num。可配成的对数取决于两者的频次较小值min(counter[remain], freq)——因为每配对一次需要同时消耗一个num和一个remain配对数量受限于较少的那一方。代码中通过if counter[remain] freq取较小者累加与min等价。以示例 1nums [1,2,3,4]、k 5为例k为奇数跳过特判遍历 map 时num 11 2配remain 4取min(1,1)1num 22 2配remain 3取min(1,1)1num 3、4均大于k/2被跳过。最终结果1 1 2与预期一致。解法二单趟在线配对原文档还提供了解法二思路是边遍历、边配对每读入一个数先登记频次再立刻检查它的补数是否已在之前的遍历中出现过。完整代码位于 1679. Max Number of K-Sum Pairs.gopackage leetcode // 解法二 func maxOperations_(nums []int, k int) int { counter, res : make(map[int]int), 0 for _, num : range nums { counter[num] remain : k - num if num remain { if counter[num] 2 { res counter[num] - 2 } } else { if counter[remain] 0 { res counter[remain]-- counter[num]-- } } } return res }逐步拆解分支一num remain即2 * num k。只有当k为偶数且当前数恰为k/2时才进入。此时需要两个相同的num才能配对因此检查counter[num] 2当前这个num刚被登记加上之前出现过的至少一个配对成功后counter[num] - 2消耗掉两个。分支二num ! remain一般情形。若补数remain在之前的遍历中出现过counter[remain] 0说明当前num可以与之前某个remain配对res记录一次操作counter[remain]--消耗一个历史补数counter[num]--则把刚登记的当前数撤销因为它已被配对使用。以示例 1nums [1,2,3,4]、k 5手动走一遍读入1counter[1] 1remain 4不存在不配对读入2counter[2] 1remain 3不存在不配对读入3counter[3] 1remain 2存在res 1counter[2] 0counter[3] 0读入4counter[4] 1remain 1存在res 2counter[1] 0counter[4] 0。最终res 2与示例 1 输出一致。值得注意的是解法二天然规避了同一数对重复计数的问题——因为配对总是发生在当前元素与更早出现的元素之间每个元素只会被消费一次无需像解法一那样依赖num k/2的手动去重。两种解法对比与复杂度分析维度解法一优化版解法二单趟配对遍历方式两趟先统计频次再遍历 map单趟边读边配对半值k/2处理特判分支 频次清零特判分支 双消耗去重策略num k/2保证每个数对只计一次在线配对天然不重复时间/空间复杂度O(n)/O(n)O(n)/O(n)两种实现的时间复杂度均为O(n)map 的均摊读写为O(1)空间复杂度均为O(n)频次表。解法一逻辑集中、易于推演正确性解法二流式处理、更贴近读一个、配一个的直觉且不需要在循环中额外维护半值清零。在数组规模达到10^5时两者都能在线性时间内完成均远优于暴力枚举的O(n²)。仓库测试用例与验证仓库为本题配备了完整的单元测试位于 1679. Max Number of K-Sum Pairs_test.go。测试采用了本仓库统一的question1679表驱动结构para1679封装输入参数nums与kans1679封装期望答案然后逐条断言maxOperations的输出。测试文件中共覆盖 4 个用例输入 numsk期望输出用例要点[1,2,3,4]52对应题目示例 1奇数k常规配对[3,1,3,4,3]62→1对应题目示例 2偶数k的半值配对[2,5,4,4,1,3,4,4,1,4,4,1,2,1,2,2,3,2,4,2]34大数组 奇数k考验去重逻辑4 对(1,2)[2,5,5,5,1,3,4,4,1,4,4,1,3,1,3,1,3,2,4,2]68偶数k全类型综合(3,3)2 对、(1,5)3 对、(2,4)3 对以最后一个用例验证解法一的半值处理counter[3] 44 1 2先计入 2 对(3,3)并清零随后num 1配5counter[5] 3计 3 对num 2配4counter[4] 5取min(5, 3) 3计 3 对总计2 3 3 8与期望输出一致。注意到测试循环中同时调用了maxOperations(p.nums, p.k)与maxOperations_(p.nums, p.k)即两个版本的实现都被实际执行验证且都会覆盖上述全部用例。在仓库中运行测试在仓库根目录执行题目目录名不含空格可直接作为路径参数go test -v -run Test_Problem1679 ./leetcode/1679.Max-Number-of-K-Sum-Pairs/-v会打印测试细节-run指定仅运行本题的Test_Problem1679测试函数。若需确认仓库全量题解均通过可运行 gotest.sh 脚本——它会对./leetcode/...下所有包一次性执行go test -covermodeatomic -coverprofilecoverage.txt生成单一合法的覆盖率文件仓库根目录的 coverage.txt 即其产物。本项目模块名为github.com/halfrost/LeetCode-GoGo 版本为 1.19见 go.mod。边界条件与易错点总结偶数k且存在k/2k/2只能与自身配对且配对后剩余单个k/2无法再与其他任何数配对。解法一通过频次整除 2 后清零处理解法二通过消耗两个counter[num]处理二者缺一不可否则会漏计或重复计数。数组元素可重复必须用频次而非布尔标记记录元素且每次配对都要消耗频次保证每个元素至多使用一次。数对去重(a, b)与(b, a)是同一个数对。解法一用num k/2约束遍历方向解法二因当前元素只与历史元素配对而天然避免。取频次较小值配对数量受限于min(counter[remain], freq)若直接取较大值会导致同一元素被重复使用。k为奇数不存在x x k的整数解半值特判分支自动跳过不影响正确性。完全没有可配对元素如nums中所有数之和都不等于kres保持 0两种实现均正确返回。小结本题是 Two Sum 家族中极具代表性的计数配对变体。LeetCode-Go 仓库中的两份 Go 实现分别展示了两种经典策略解法一统计频次后统一配对以num k/2与半值清零两个关键技巧保证每个数对恰好计数一次解法二单趟在线配对则利用流式处理的天然优势规避去重问题。二者时间复杂度均为O(n)配合仓库内 4 组覆盖偶数/奇数k、重复元素、大数组场景的单元测试读者可以快速验证算法正确性并将该频次哈希 补数查找模式迁移到其他配对类问题如三数之和的配对子问题、字符串字符配对统计等中。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
