leetcode
leetcode 1651 ~ 1700
找出和为指定值的下标对

找出和为指定值的下标对

难度:

标签:

题目描述

代码结果

运行时间: 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`的元素出现次数是否会对后续添加操作的效率产生影响?
在构造函数中直接计算`nums1`和`nums2`的元素出现次数,本身是为了后续操作提供效率。通过预先计算这些频次,`count`方法可以迅速通过哈希表查找而非遍历数组来确定元素频次,从而显著提高查询效率。对于`add`操作,虽然需要更新`nums2`的元素值及其频次,但这种更新是局部的(只影响一个元素的频次),因此不会显著影响整体效率。综上,构造函数中的预计算对后续操作的效率影响是正面的,尽管`add`操作需要额外处理,但这是可控的。
🦆
当`nums2`数组在`add`操作中频繁更新时,是否存在一种更高效的方法来维护`D2`计数器,以提高性能?
如果`nums2`数组在`add`操作中频繁更新,一个可能的优化是使用更高效的数据结构,如平衡树(如AVL树或红黑树)来维护元素及其频次。这些数据结构能在对数时间内完成插入、删除和查找操作,相比哈希表在频繁更新时可能更稳定。此外,考虑到`add`操作的局部性,可以引入延迟更新策略,在实际需要计数结果时再进行必要的更新,从而减少更新操作的次数。
🦆
在`count`方法中,为什么选择遍历`D1`而不是`D2`来寻找匹配的元素,是否与`nums1`和`nums2`的长度有关?
选择遍历`D1`而不是`D2`的原因可能与`nums1`和`nums2`的长度有关。理想情况下,我们应该遍历较小的字典,因为这样做可以减少查找操作的次数。如果`nums1`的元素种类较少(即`D1`比`D2`小),遍历`D1`将更高效。此外,由于`D1`在整个对象生命周期中保持不变,而`D2`可能因`add`操作而改变,保持`D1`作为遍历基准可以提供更稳定的性能。

相关问题