找出和为指定值的下标对
难度:
标签:
题目描述
代码结果
运行时间: 256 ms, 内存: 45.9 MB
import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;
/**
* 思路:
* 1. 使用 nums1 初始化一个数组。
* 2. 使用 nums2 初始化一个数组并且使用 HashMap 来存储其元素的频率。
* 3. add 方法在 nums2 上增加值并更新 HashMap 中的频率。
* 4. count 方法使用 Java Stream API 遍历 nums1,计算满足 nums1[i] + nums2[j] == tot 的配对数。
*/
public class FindSumPairs {
private int[] nums1;
private int[] nums2;
private Map<Integer, Integer> freqMap;
public FindSumPairs(int[] nums1, int[] nums2) {
this.nums1 = nums1;
this.nums2 = nums2;
this.freqMap = new HashMap<>();
for (int num : nums2) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
}
public void add(int index, int val) {
int oldVal = nums2[index];
nums2[index] += val;
freqMap.put(oldVal, freqMap.get(oldVal) - 1);
if (freqMap.get(oldVal) == 0) {
freqMap.remove(oldVal);
}
freqMap.put(nums2[index], freqMap.getOrDefault(nums2[index], 0) + 1);
}
public int count(int tot) {
return IntStream.of(nums1)
.map(num1 -> tot - num1)
.map(complement -> freqMap.getOrDefault(complement, 0))
.sum();
}
}
解释
方法:
该题解通过维护两个计数器(哈希表),D1 和 D2,分别用于统计数组 nums1 和 nums2 中各元素的出现次数。初始化时,直接计算 nums1 和 nums2 中元素的出现次数。在执行 add 操作时,更新 nums2 数组中指定位置的元素值,并相应地调整 D2 中的计数。在执行 count 操作时,遍历 D1 中的每个元素 x,计算 tot-x 在 D2 中是否存在,若存在,则将符合条件的下标对的计数乘以 x 在 nums1 中的出现次数,并累加到结果中。这样可以快速统计符合条件的下标对数量。
时间复杂度:
O(m)
空间复杂度:
O(n + m)(n 和 m 分别是 nums1 和 nums2 的长度)
代码细节讲解
🦆
在`FindSumPairs`类的构造函数中,直接计算`nums1`和`nums2`的元素出现次数是否会对后续添加操作的效率产生影响?
▷🦆
当`nums2`数组在`add`操作中频繁更新时,是否存在一种更高效的方法来维护`D2`计数器,以提高性能?
▷🦆
在`count`方法中,为什么选择遍历`D1`而不是`D2`来寻找匹配的元素,是否与`nums1`和`nums2`的长度有关?
▷