找出和为指定值的下标对

难度: Medium

给你两个整数数组 nums1 和 nums2 ，请你实现一个支持下述两类查询的数据结构：

累加，将一个正整数加到 nums2 中指定下标对应元素上。
计数，统计满足 nums1[i] + nums2[j] 等于指定值的下标对 (i, j) 数目（0 <= i < nums1.length 且 0 <= j < nums2.length）。

实现 FindSumPairs 类：

FindSumPairs(int[] nums1, int[] nums2) 使用整数数组 nums1 和 nums2 初始化 FindSumPairs 对象。
void add(int index, int val) 将 val 加到 nums2[index] 上，即，执行 nums2[index] += val 。
int count(int tot) 返回满足 nums1[i] + nums2[j] == tot 的下标对 (i, j) 数目。

示例：

输入：
["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"]
[[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]]
输出：
[null, 8, null, 2, 1, null, null, 11]

解释：
FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);
findSumPairs.count(7);  // 返回 8 ; 下标对 (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) 满足 2 + 5 = 7 ，下标对 (5,1), (5,5) 满足 3 + 4 = 7
findSumPairs.add(3, 2); // 此时 nums2 = [1,4,5,4,5,4]
findSumPairs.count(8);  // 返回 2 ；下标对 (5,2), (5,4) 满足 3 + 5 = 8
findSumPairs.count(4);  // 返回 1 ；下标对 (5,0) 满足 3 + 1 = 4
findSumPairs.add(0, 1); // 此时 nums2 = [2,4,5,4,5,4]
findSumPairs.add(1, 1); // 此时 nums2 = [2,5,5,4,5,4]
findSumPairs.count(7);  // 返回 11 ；下标对 (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) 满足 2 + 5 = 7 ，下标对 (5,3), (5,5) 满足 3 + 4 = 7

提示：

1 <= nums1.length <= 1000
1 <= nums2.length <= 10⁵
1 <= nums1[i] <= 10⁹
1 <= nums2[i] <= 10⁵
0 <= index < nums2.length
1 <= val <= 10⁵
1 <= tot <= 10⁹
最多调用 add 和 count 函数各 1000 次

Submission

运行时间: 256 ms

内存: 45.9 MB

class FindSumPairs:

    def __init__(self, nums1: List[int], nums2: List[int]):
        self.nums2 = nums2
        self.D1 = Counter(nums1)
        self.D2 = Counter(nums2)

    def add(self, index: int, val: int) -> None:
        x = self.nums2[index]
        self.D2[x] -= 1
        self.nums2[index] += val
        self.D2[x+val] += 1

    def count(self, tot: int) -> int:
        res = 0
        for x in self.D1:
            if tot-x in self.D2:
                res += self.D1[x]*self.D2[tot-x]
        return res


# Your FindSumPairs object will be instantiated and called as such:
# obj = FindSumPairs(nums1, nums2)
# obj.add(index,val)
# param_2 = obj.count(tot)

Explain

该题解通过维护两个计数器（哈希表），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 的长度）

# 类定义

class FindSumPairs:

    def __init__(self, nums1: List[int], nums2: List[int]):
        self.nums2 = nums2  # 保存 nums2 数组，用于 add 操作
        self.D1 = Counter(nums1)  # nums1 中元素的频次
        self.D2 = Counter(nums2)  # nums2 中元素的频次

    def add(self, index: int, val: int) -> None:
        x = self.nums2[index]  # 取得修改前的值
        self.D2[x] -= 1  # 更新旧值频次
        self.nums2[index] += val  # 更新 nums2 数组
        self.D2[x+val] += 1  # 更新新值频次

    def count(self, tot: int) -> int:
        res = 0  # 用于累计满足条件的下标对数
        for x in self.D1:
            if tot-x in self.D2:
                res += self.D1[x] * self.D2[tot-x]  # 计算符合条件的下标对并累加
        return res

# 使用示例
# obj = FindSumPairs(nums1, nums2)
# obj.add(index, val)
# param_2 = obj.count(tot)

Explore

在构造函数中直接计算`nums1`和`nums2`的元素出现次数，本身是为了后续操作提供效率。通过预先计算这些频次，`count`方法可以迅速通过哈希表查找而非遍历数组来确定元素频次，从而显著提高查询效率。对于`add`操作，虽然需要更新`nums2`的元素值及其频次，但这种更新是局部的（只影响一个元素的频次），因此不会显著影响整体效率。综上，构造函数中的预计算对后续操作的效率影响是正面的，尽管`add`操作需要额外处理，但这是可控的。

如果`nums2`数组在`add`操作中频繁更新，一个可能的优化是使用更高效的数据结构，如平衡树（如AVL树或红黑树）来维护元素及其频次。这些数据结构能在对数时间内完成插入、删除和查找操作，相比哈希表在频繁更新时可能更稳定。此外，考虑到`add`操作的局部性，可以引入延迟更新策略，在实际需要计数结果时再进行必要的更新，从而减少更新操作的次数。

选择遍历`D1`而不是`D2`的原因可能与`nums1`和`nums2`的长度有关。理想情况下，我们应该遍历较小的字典，因为这样做可以减少查找操作的次数。如果`nums1`的元素种类较少（即`D1`比`D2`小），遍历`D1`将更高效。此外，由于`D1`在整个对象生命周期中保持不变，而`D2`可能因`add`操作而改变，保持`D1`作为遍历基准可以提供更稳定的性能。