1865. 找出和为指定值的下标对
题目描述
给你两个整数数组 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 <= 10001 <= nums2.length <= 1051 <= nums1[i] <= 1091 <= nums2[i] <= 1050 <= index < nums2.length1 <= val <= 1051 <= tot <= 109- 最多调用
add和count函数各1000次
解法
方法一：哈希表
我们注意到，数组 $\textit{nums1}$ 的长度不超过 ${10}^3$，数组 $\textit{nums2}$ 的长度达到 ${10}^5$，因此，如果直接暴力枚举所有下标对 $(i, j)$，计算 $\textit{nums1}[i] + \textit{nums2}[j]$ 是否等于指定值 $\textit{tot}$，那么会超出时间限制。
能否只枚举长度较短的数组 $\textit{nums1}$ 呢？答案是可以的。我们用一个哈希表 $\textit{cnt}$ 统计数组 $\textit{nums2}$ 中每个元素出现的次数，然后枚举数组 $\textit{nums1}$ 中的每个元素 $x$，计算 $\textit{cnt}[\textit{tot} - x]$ 的值之和即可。
在调用 $\text{add}$ 方法时，我们需要先将 $\textit{nums2}[index]$ 对应的值从 $\textit{cnt}$ 中减去 $1$，然后将 $\textit{nums2}[index]$ 的值加上 $\textit{val}$，最后将 $\textit{nums2}[index]$ 对应的值加上 $1$。
在调用 $\text{count}$ 方法时，我们只需要遍历数组 $\textit{nums1}$，对于每个元素 $x$，计算 $\textit{cnt}[\textit{tot} - x]$ 的值之和即可。
时间复杂度 $O(n \times q)$，空间复杂度 $O(m)$。其中 $n$ 和 $m$ 分别是数组 $\textit{nums1}$ 和 $\textit{nums2}$ 的长度，而 $q$ 是调用 $\text{count}$ 方法的次数。
Python3
class FindSumPairs:
def __init__(self, nums1: List[int], nums2: List[int]):
self.cnt = Counter(nums2)
self.nums1 = nums1
self.nums2 = nums2
def add(self, index: int, val: int) -> None:
self.cnt[self.nums2[index]] -= 1
self.nums2[index] += val
self.cnt[self.nums2[index]] += 1
def count(self, tot: int) -> int:
return sum(self.cnt[tot - x] for x in self.nums1)
# Your FindSumPairs object will be instantiated and called as such:
# obj = FindSumPairs(nums1, nums2)
# obj.add(index,val)
# param_2 = obj.count(tot)
Java
class FindSumPairs {
private int[] nums1;
private int[] nums2;
private Map<Integer, Integer> cnt = new HashMap<>();
public FindSumPairs(int[] nums1, int[] nums2) {
this.nums1 = nums1;
this.nums2 = nums2;
for (int x : nums2) {
cnt.merge(x, 1, Integer::sum);
}
}
public void add(int index, int val) {
cnt.merge(nums2[index], -1, Integer::sum);
nums2[index] += val;
cnt.merge(nums2[index], 1, Integer::sum);
}
public int count(int tot) {
int ans = 0;
for (int x : nums1) {
ans += cnt.getOrDefault(tot - x, 0);
}
return ans;
}
}
/**
* Your FindSumPairs object will be instantiated and called as such:
* FindSumPairs obj = new FindSumPairs(nums1, nums2);
* obj.add(index,val);
* int param_2 = obj.count(tot);
*/
C++
class FindSumPairs {
public:
FindSumPairs(vector<int>& nums1, vector<int>& nums2) {
this->nums1 = nums1;
this->nums2 = nums2;
for (int x : nums2) {
++cnt[x];
}
}
void add(int index, int val) {
--cnt[nums2[index]];
nums2[index] += val;
++cnt[nums2[index]];
}
int count(int tot) {
int ans = 0;
for (int x : nums1) {
ans += cnt[tot - x];
}
return ans;
}
private:
vector<int> nums1;
vector<int> nums2;
unordered_map<int, int> cnt;
};
/**
* Your FindSumPairs object will be instantiated and called as such:
* FindSumPairs* obj = new FindSumPairs(nums1, nums2);
* obj->add(index,val);
* int param_2 = obj->count(tot);
*/
Go
type FindSumPairs struct {
nums1 []int
nums2 []int
cnt map[int]int
}
func Constructor(nums1 []int, nums2 []int) FindSumPairs {
cnt := map[int]int{}
for _, x := range nums2 {
cnt[x]++
}
return FindSumPairs{nums1, nums2, cnt}
}
func (this *FindSumPairs) Add(index int, val int) {
this.cnt[this.nums2[index]]--
this.nums2[index] += val
this.cnt[this.nums2[index]]++
}
func (this *FindSumPairs) Count(tot int) (ans int) {
for _, x := range this.nums1 {
ans += this.cnt[tot-x]
}
return
}
/**
* Your FindSumPairs object will be instantiated and called as such:
* obj := Constructor(nums1, nums2);
* obj.Add(index,val);
* param_2 := obj.Count(tot);
*/
TypeScript
class FindSumPairs {
private nums1: number[];
private nums2: number[];
private cnt: Map<number, number>;
constructor(nums1: number[], nums2: number[]) {
this.nums1 = nums1;
this.nums2 = nums2;
this.cnt = new Map();
for (const x of nums2) {
this.cnt.set(x, (this.cnt.get(x) || 0) + 1);
}
}
add(index: number, val: number): void {
const old = this.nums2[index];
this.cnt.set(old, this.cnt.get(old)! - 1);
this.nums2[index] += val;
const now = this.nums2[index];
this.cnt.set(now, (this.cnt.get(now) || 0) + 1);
}
count(tot: number): number {
return this.nums1.reduce((acc, x) => acc + (this.cnt.get(tot - x) || 0), 0);
}
}
/**
* Your FindSumPairs object will be instantiated and called as such:
* var obj = new FindSumPairs(nums1, nums2)
* obj.add(index,val)
* var param_2 = obj.count(tot)
*/
JavaScript
/**
* @param {number[]} nums1
* @param {number[]} nums2
*/
var FindSumPairs = function (nums1, nums2) {
this.nums1 = nums1;
this.nums2 = nums2;
this.cnt = new Map();
for (const x of nums2) {
this.cnt.set(x, (this.cnt.get(x) || 0) + 1);
}
};
/**
* @param {number} index
* @param {number} val
* @return {void}
*/
FindSumPairs.prototype.add = function (index, val) {
const old = this.nums2[index];
this.cnt.set(old, this.cnt.get(old) - 1);
this.nums2[index] += val;
const now = this.nums2[index];
this.cnt.set(now, (this.cnt.get(now) || 0) + 1);
};
/**
* @param {number} tot
* @return {number}
*/
FindSumPairs.prototype.count = function (tot) {
return this.nums1.reduce((acc, x) => acc + (this.cnt.get(tot - x) || 0), 0);
};
/**
* Your FindSumPairs object will be instantiated and called as such:
* var obj = new FindSumPairs(nums1, nums2)
* obj.add(index,val)
* var param_2 = obj.count(tot)
*/
C#
public class FindSumPairs {
private int[] nums1;
private int[] nums2;
private Dictionary<int, int> cnt = new Dictionary<int, int>();
public FindSumPairs(int[] nums1, int[] nums2) {
this.nums1 = nums1;
this.nums2 = nums2;
foreach (int x in nums2) {
if (cnt.ContainsKey(x)) {
cnt[x]++;
} else {
cnt[x] = 1;
}
}
}
public void Add(int index, int val) {
int oldVal = nums2[index];
if (cnt.TryGetValue(oldVal, out int oldCount)) {
if (oldCount == 1) {
cnt.Remove(oldVal);
} else {
cnt[oldVal] = oldCount - 1;
}
}
nums2[index] += val;
int newVal = nums2[index];
if (cnt.TryGetValue(newVal, out int newCount)) {
cnt[newVal] = newCount + 1;
} else {
cnt[newVal] = 1;
}
}
public int Count(int tot) {
int ans = 0;
foreach (int x in nums1) {
int target = tot - x;
if (cnt.TryGetValue(target, out int count)) {
ans += count;
}
}
return ans;
}
}
/**
* Your FindSumPairs object will be instantiated and called as such:
* FindSumPairs obj = new FindSumPairs(nums1, nums2);
* obj.Add(index,val);
* int param_2 = obj.Count(tot);
*/