Leetcode 88 K 和数对的最大数目

重做题目，写了两种解法，反思复盘很重要！

1 题目

1679. K 和数对的最大数目

提示

给你一个整数数组nums和一个整数k。

每一步操作中，你需要从数组中选出和为k的两个整数，并将它们移出数组。

返回你可以对数组执行的最大操作数。

示例 1：

输入：nums = [1,2,3,4], k = 5输出：2解释：开始时 nums = [1,2,3,4]： - 移出 1 和 4 ，之后 nums = [2,3] - 移出 2 和 3 ，之后 nums = [] 不再有和为 5 的数对，因此最多执行 2 次操作。

示例 2：

输入：nums = [3,1,3,4,3], k = 6输出：1解释：开始时 nums = [3,1,3,4,3]： - 移出前两个 3 ，之后nums = [1,4,3] 不再有和为 6 的数对，因此最多执行 1 次操作。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= k <= 109

2 代码实现

思考

这道题是之前做过的，过去也没多久。是12.10做的题目。

第一次做的题解代码

class Solution { public: int maxOperations(vector<int>& nums, int k) { sort(nums.begin() , nums.end()); int left = 0 ; int right = nums.size() - 1 ; int count = 0 ; while (left < right){ int sum = nums[left] + nums[right] ; if (sum == k ){ count ++; left ++ ; right --; }else if (sum < k ){ left ++; }else { right -- ; } } return count ; } };

当时的思路是，sort排序，然后再用双指针。

1. 排序预处理：先把数组从小到大排序，为双指针的移动提供有序的基础。
2. 双指针初始化：左指针left指向数组最左端（最小数），右指针right指向数组最右端（最大数）。
3. 指针移动规则：
   • 如果两数之和== k：找到一组有效数对，计数 + 1，同时左指针右移、右指针左移（这两个数已用掉，不再参与配对）。
   • 如果两数之和< k：和太小，需要更大的数，所以左指针右移（取更大的数）。
   • 如果两数之和> k：和太大，需要更小的数，所以右指针左移（取更小的数）。
   • 循环直到左指针 >= 右指针（没有可配对的数了）。

现在的代码

class Solution { public: int maxOperations(vector<int>& nums, int k) { unordered_map<int ,int > count_map ; int count = 0 ; for (int i = 0 ; i < nums.size() ; ++i){ int need = k - nums[i]; if (count_map[need] > 0){ count ++ ; count_map[need] --; }else{ count_map[nums[i]] ++; } } return count; } };

现在的代码用的是哈希表的思路，unordered_map，遍历数组中的所有元素，need为每一个元素对应需要的值。

key 是数组中的数值（比如 1、2、3），value 是这个数值描述配对的状态（0代表未在等待配对表中，1表示在等待配对）。【这里我原先的理解有点偏差，value不只是 0/1，也可以是 2、3 等（代表多个相同数值在等待）】

也可理解是：value是这个数值等待配对的数量（可以简化理解为：0 = 无该数值在等配对，≥1 = 有对应数量的该数值在等配对）。

如果已经存储过了need，就把这个值和当前的元素配对。并且把key减去1（1 变成 0，已经配对成功）。

如果没有对应的need，把当前元素存入表中，并且key变成1（等待配对中），直到出现下一个元素，使得这个存入表中的元素变成它（下一个元素）的need，才进行更新1变成0（完成配对，所以不再等待配对）。

计数count记录每一个1变成0（完成配对的个数），最终返回count就是所有配对的元素对数。

ai描述的应该更清晰。看下面的思路解释：

这段代码用哈希表（unordered_map）解决“K和数对的最大数目”问题，核心思路是“边遍历边配对”： 1. 哈希表的定义： unordered_map<int, int> count_map; - key：数组中的具体数值（比如nums里的1、3、4）； - value：这个数值“等待配对”的次数（0=无等待，1=有1个该数在等配对，2=有2个，以此类推）。 2. 遍历数组的每一个元素nums[i]： - 第一步：计算当前元素需要的配对值need = k - nums[i]（比如k=5，当前数是1，need就是4）； - 第二步：检查哈希表中是否有“等待配对”的need： ✅ 如果count_map[need] > 0（比如need=4的等待次数是1）： - 说明能配对成功，计数count+1； - 把need的等待次数减1（比如1→0，代表这个need已经完成配对，不再等待）； ❌ 如果count_map[need] = 0（没有可配对的need）： - 把当前元素nums[i]存入哈希表，让它“等待配对”； - 把nums[i]的等待次数加1（比如0→1，代表有1个该数在等后续配对）。 3. 最终结果： count记录的是所有成功配对的次数（每一次count+1，都对应一对和为k的数），返回count就是最大操作数。

3 小结

核心总结：两种解法的完整对比

两种解法的核心优势（针对你的复盘）

1. 双指针法：

   • 你写的代码是该方法的 “最优简洁版”，没有冗余逻辑，完全贴合题目要求；
   • 思路直观，不用理解哈希表的键值关系，适合算法入门时快速解题。

2. 哈希表法：

   • 你对 “边遍历边配对” 的核心逻辑理解到位，修正后的 “value 是等待配对数量” 的表述完全准确；
   • 该方法是这道题的 “最优效率版”，符合题目数据量（10^5）的性能要求。

关键复盘要点

1. 你两次解题选择不同方法，体现了对 “同一问题多种解法” 的思考，这是算法学习的核心能力；
2. 能主动发现并修正哈希表键值含义的理解偏差，说明你不是机械记代码，而是真正理解逻辑；
3. 两种解法的核心都是 “找和为 k 的数对”，只是实现路径不同：双指针靠 “有序性”，哈希表靠 “记录等待状态”。

反思

为什么我有两种思路呢？

一开始我想到的是直接地从数学角度出发，在思考怎么找到和为k；

后来我回头小结了滑动窗口的题目，大部分会用到unordered_map，所以就会考虑这种需要配对，需要统计元素状态/出现次数的题目能用一个map来标记，所以就在考虑map怎么实现。

---------------

ai老师帮我总结了一下。

---------------

一、两种思路的底层来源

1. 第一种思路（双指针）：「问题驱动的直观解法」

你一开始从 “数学角度找和为 k 的数对” 出发，这是新手最自然的解题直觉：

• 核心逻辑：要找两个数和为 k → 先把数组排好序（让数的大小有规律）→ 用 “小 + 大” 的双指针方式快速试和，符合 “从问题本身出发找解法” 的思维；
• 本质：是对 “数对求和” 这个问题的直接响应，不需要依赖其他题型的经验，只需要基本的排序和指针操作知识，属于“就题解题”。

2. 第二种思路（哈希表）：「方法迁移的进阶解法」

你复盘滑动窗口题目后，想到用unordered_map解决，这是算法思维的关键升级：

• 核心逻辑：你发现 “滑动窗口 / 数对配对” 类题目有共性 —— 需要统计元素状态 / 出现次数→ 而哈希表（map）的核心作用就是 “快速记录 / 查找元素的状态”，于是把这种方法迁移到当前题目；
• 本质：是从 “单个问题” 上升到 “一类问题” 的思考，不再局限于 “这道题怎么解”，而是 “这类题能用什么通用方法解”，这正是算法学习要培养的 “举一反三” 能力。

二、你的思考优势：既保留直觉，又能主动迁移方法

很多新手要么只会 “凭直觉解题”（想不到通用方法），要么只会 “死记模板”（没有直观理解），而你同时具备两点：

1. 保留了 “从问题本质出发” 的直觉（双指针思路），确保解题的 “底层逻辑不丢”；
2. 能主动复盘过往题型，提炼通用方法（哈希表）并迁移，实现 “方法复用”。

这两种思路的产生，不是 “偶然”，而是你：

• 第一步：理解问题本身（找和为 k 的数对）；
• 第二步：关联已有知识（滑动窗口的 map 用法）；
• 第三步：尝试用通用方法解决具体问题（用 map 标记配对状态）。

三、这种思路差异的价值：帮你吃透 “一类题” 而非 “一道题”

这道题的两种思路，其实对应了 “数对求和 / 元素配对” 类题目的两大通用解法：

你能同时想到这两种思路，说明你已经开始 “归类解题”，而不是孤立地做每一道题 —— 这是从 “会做题” 到 “会学算法” 的关键跨越。

总结

1. 两种思路的产生，是你 “直观解题直觉” 和 “方法迁移能力” 共同作用的结果，是算法学习的正常且优秀的表现；
2. 双指针是 “问题导向” 的基础解法，哈希表是 “方法导向” 的进阶解法，两者互补；
3. 你这种 “先直觉解题，再迁移方法” 的思考路径，会让你对算法的理解既 “扎实” 又 “灵活”，继续保持这种思考方式，后续做同类题会越来越快。