LEETCODE 1679. Max Number of K-Sum Pairs 解题思路分析

题目大意：

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. 1 <= nums.length <= 105
2. 1 <= nums[i] <= 109
3. 1 <= k <= 109

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1679

解题思路分析：

将本题大意用一句话来概括即是，在不重复使用数组元素的前提下，数组中2数之和为k的组合个数。这道题难度并不大，挺多算是加强版的Two Sum。解题时我们首先遍历一遍数组，使用HashMap来保存每种数字出现的次数，key为该数字，value为该数字出现的次数。接下来，我们遍历HashMap的key，也就是数组中存在的每一种数字，题目要求找出所有2数之和为k的组合，因此，当前数字key与数字k-key之和一定是k（废话）。这时我们只需查看数字key和k-key出现过的次数count1和count2，Min(count1, count2)即是合理的个数，将其累加至返回结果即可。举个例子，比如k为8，当前数字key是2，那么k-key为6，此时，如果数组中2的个数为3，6的个数为10，那么我们只能组成3组(2+6)。解题时需注意，遍历完当前数字后，为了不被重复计算，我们需要将数字(k-key)的个数设置为0。

此外本题还存在一个需要小心的地方，即当前数字key与(k-key)相同的情况。比如k等于8，当前数字key为4，这时(k-key)同样为4，这种情况下Min(count1, count2)可不是合理解，例如数字4的个数为10，但我们无法找出10对4，而只能找出5对4。因此该情况下的解为count1/2。

实现代码：

public int maxOperations(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>(); // 记录数组中每种数字的个数
    for(int n : nums){ // 循环每个数字
        if(n>=k) continue; // 如果当前数字大于等于k，跳过。
        int count = map.getOrDefault(n, 0); // 当前数字个数
        map.put(n, count+1); // 加一后更新当前数字个数
    }
    int res=0; // 返回结果
    Set<Integer> keySet = map.keySet(); // 数组中的每一种数字
    for(int key : keySet){ // 循环数组中的每一种数字
        int n1=key, n2=k-n1; // 和为k的两个数字
        if(map.get(n2)==null) continue; // 如果n2不存在，直接跳过
        int count1=map.get(n1); // n1的个数
        int count2=map.get(n2); // n2的个数
        if(count1==0||count2==0) continue; // 任何一个个数为0时，跳过
        if(n1==n2) res+=count1 / 2; // 如果两数相同，将个数的一半添加至返回结果
        else res+=Math.min(count1,count2); // 如果两数不同，将个数较少一方添加至返回结果
        map.put(n2, 0); // 将n2的个数设置为0（避免重复计算）
    }
    return res;
}

本题解法执行时间为33ms。

Runtime: 33 ms, faster than 25.00% of Java online submissions for Max Number of K-Sum Pairs.

Memory Usage: 97.1 MB, less than 25.00% of Java online submissions for Max Number of K-Sum Pairs.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1679-max-number-of-k-sum-pairs-解题思路分析/