leetcode
leetcode 1501 ~ 1550
K 和数对的最大数目

K 和数对的最大数目

难度:

标签:

题目描述

代码结果

运行时间: 62 ms, 内存: 28.2 MB


/*
 * 题目思路:
 * 1. 使用 Java Stream 对数组进行处理。
 * 2. 使用哈希表来存储数组中每个数字出现的次数。
 * 3. 遍历数组,对于每个数字,计算它与 k 之间的差值。
 * 4. 检查这个差值是否在哈希表中存在,且其出现次数大于0。
 * 5. 如果存在,将当前数字和差值的次数减一,并增加一次操作计数。
 * 6. 返回操作计数。
 */

import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;

public class Solution {
    public int maxOperations(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        final int[] count = {0};
        IntStream.of(nums).forEach(num -> {
            int complement = k - num;
            if (map.getOrDefault(complement, 0) > 0) {
                count[0]++;
                map.put(complement, map.get(complement) - 1);
            } else {
                map.put(num, map.getOrDefault(num, 0) + 1);
            }
        });
        return count[0];
    }
}

解释

方法:

本题解使用哈希表来存储数组中每个数字的出现次数,然后遍历哈希表的键(即数组中的不同数字),检查每个数字与其配对构成和为k的另一个数字是否存在于哈希表中。对于每个数字num,如果num的两倍小于k,则检查与之相加等于k的数字(即k-num)是否存在,并将它们的出现次数的最小值累加到答案中。如果num的两倍恰好等于k,说明需要将num与自身配对,只能将其出现次数除以2(向下取整)来计算配对的次数。遍历完成后,得到的答案即为最大操作数。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在哈希表中检查配对数字时,如何处理已被配对的数字以避免重复计数?
在算法实现中,我们通过确保每次处理数字num时,只考虑其配对数字k-num,且仅当num小于k-num时才进行配对操作,以避免重复计数。这意味着,对于每一对有效的配对数字,它们只会被计算一次。例如,当num等于k-num时,如num * 2 = k,我们通过直接将num的数量除以2来处理配对,确保每个数字只与自己配对一次,不会与其他数字重复配对。
🦆
为什么在num * 2等于k的情况下,只考虑将num的数量除以2而不是考虑其他可能的配对数字?
当num * 2等于k时,这意味着num只能与自身形成有效配对,因为其他任何数字加上num都将超过k或小于k,无法形成有效的k-sum配对。因此,在这种特定情况下,只考虑将num的数量除以2来计算配对次数,每两个相同的num可以形成一次有效操作。这种方法确保了算法的准确性和效率。
🦆
在实现中,如果配对的数字k-num不存在于哈希表中,为什么使用tmp.get(k-num, 0)而不是直接访问tmp[k-num]?
在Python中,使用tmp.get(k-num, 0)可以安全地尝试访问哈希表中的元素,即使该元素不存在也不会引发错误。如果使用tmp[k-num],当k-num不在哈希表中时,将引发KeyError异常。使用get方法允许我们为不存在的键提供一个默认值(在本例中为0),这使得代码更加健壮,能够处理数组中不存在的数字,简化了配对逻辑。
🦆
如何确保在遍历哈希表时,对于每对数字的配对操作只计算一次,特别是当num不等于k-num时?
为了确保每对数字只被计算一次,算法在遍历哈希表时采取了特殊策略:只考虑那些num小于k-num的情况进行计数。这样做确保了每一对数字(num和k-num)只在num的迭代时被计算一次,避免在k-num的迭代时重复计算。此外,当num恰好等于k-num时,我们通过将num的数量除以2来处理,确保这种情况下的配对也只计算一次。这种策略避免了重复和冗余的计算,提高了算法的效率和准确性。

相关问题