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 * 2等于k的情况下,只考虑将num的数量除以2而不是考虑其他可能的配对数字?
▷🦆
在实现中,如果配对的数字k-num不存在于哈希表中,为什么使用tmp.get(k-num, 0)而不是直接访问tmp[k-num]?
▷🦆
如何确保在遍历哈希表时,对于每对数字的配对操作只计算一次,特别是当num不等于k-num时?
▷