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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。