Medium

题目描述

给你两个整数数组 nums1 和 nums2。你需要实现一个数据结构，支持以下两种类型的查询：

  1. 将一个正整数加到 nums2 中给定索引处的元素上。
  2. 统计满足 nums1[i] + nums2[j] == target 的数对 (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) 数目。

示例 1：

输入：
["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]

提示：

  • 1 <= nums1.length <= 1000
  • 1 <= nums2.length <= 10^5
  • 1 <= nums1[i] <= 10^9
  • 1 <= nums2[i] <= 10^5
  • 0 <= index < nums2.length
  • 1 <= val <= 10^5
  • 1 <= tot <= 10^9
  • 最多调用 add 和 count 方法 1000 次

解题思路

这道题的关键在于利用 nums1 长度较小的特点来优化查询效率。

核心思路：

  1. 由于 nums1 长度最多 1000，而 nums2 长度可达 10^5，我们应该以 nums1 为主导来设计算法
  2. 使用哈希表记录 nums2 中每个元素的出现次数，这样可以快速查询特定值的个数
  3. 对于 count 操作，遍历 nums1 中的每个元素 x，在哈希表中查找 tot - x 的出现次数

具体实现：

  • 初始化时，用哈希表统计 nums2 中每个数字的频次
  • add 操作：更新 nums2[index] 的值，同时维护哈希表中对应的频次
  • count 操作：遍历 nums1，对每个元素 nums1[i]，在哈希表中查找 tot - nums1[i] 的出现次数并累加

时间复杂度分析：

  • 初始化：O(nums2.length)
  • add 操作：O(1)
  • count 操作：O(nums1.length)，由于 nums1.length ≤ 1000，这比直接遍历 nums2 要高效得多

这种方法充分利用了题目给出的约束条件，是一个典型的以空间换时间的优化策略。

代码实现

class FindSumPairs {
private:
    vector<int> nums1, nums2;
    unordered_map<int, int> freq;
    
public:
    FindSumPairs(vector<int>& nums1, vector<int>& nums2) {
        this->nums1 = nums1;
        this->nums2 = nums2;
        for (int num : nums2) {
            freq[num]++;
        }
    }
    
    void add(int index, int val) {
        freq[nums2[index]]--;
        nums2[index] += val;
        freq[nums2[index]]++;
    }
    
    int count(int tot) {
        int result = 0;
        for (int num : nums1) {
            int target = tot - num;
            if (freq.count(target)) {
                result += freq[target];
            }
        }
        return result;
    }
};

class FindSumPairs:

    def __init__(self, nums1: List[int], nums2: List[int]):
        self.nums1 = nums1
        self.nums2 = nums2
        self.freq = {}
        for num in nums2:
            self.freq[num] = self.freq.get(num, 0) + 1

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

    def count(self, tot: int) -> int:
        result = 0
        for num in self.nums1:
            target = tot - num
            if target in self.freq:
                result += self.freq[target]
        return result

public class FindSumPairs {
    private int[] nums1;
    private int[] nums2;
    private Dictionary<int, int> freq;

    public FindSumPairs(int[] nums1, int[] nums2) {
        this.nums1 = nums1;
        this.nums2 = nums2;
        this.freq = new Dictionary<int, int>();
        foreach (int num in nums2) {
            if (freq.ContainsKey(num)) {
                freq[num]++;
            } else {
                freq[num] = 1;
            }
        }
    }
    
    public void Add(int index, int val) {
        freq[nums2[index]]--;
        nums2[index] += val;
        if (freq.ContainsKey(nums2[index])) {
            freq[nums2[index]]++;
        } else {
            freq[nums2[index]] = 1;
        }
    }
    
    public int Count(int tot) {
        int result = 0;
        foreach (int num in nums1) {
            int target = tot - num;
            if (freq.ContainsKey(target)) {
                result += freq[target];
            }
        }
        return result;
    }
}

var FindSumPairs = function(nums1, nums2) {
    this.nums1 = nums1;
    this.nums2 = nums2;
    this.freq = new Map();
    for (let num of nums2) {
        this.freq.set(num, (this.freq.get(num) || 0) + 1);
    }
};

FindSumPairs.prototype.add = function(index, val) {
    this.freq.set(this.nums2[index], this.freq.get(this.nums2[index]) - 1);
    this.nums2[index] += val;
    this.freq.set(this.nums2[index], (this.freq.get(this.nums2[index]) || 0) + 1);
};

FindSumPairs.prototype.count = function(tot) {
    let result = 0;
    for (let num of this.nums1) {
        let target = tot - num;
        if (this.freq.has(target)) {
            result += this.freq.get(target);
        }
    }
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
初始化O(nums2.length)O(nums2中不同元素个数)
addO(1)O(1)
countO(nums1.length)O(1)

总体空间复杂度：O(nums2中不同元素个数)，最坏情况下为 O(nums2.length)

相关题目