登录[Python3/Java/C++/Go/TypeScript] 一题一解：哈希表（清晰题解）
方法一：哈希表
我们注意到，数组 $\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]$ 的值之和即可。
###python
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);
*/
###cpp
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);
*/
###ts
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)
*/
###rust
use std::collections::HashMap;
struct FindSumPairs {
nums1: Vec<i32>,
nums2: Vec<i32>,
cnt: HashMap<i32, i32>,
}
impl FindSumPairs {
fn new(nums1: Vec<i32>, nums2: Vec<i32>) -> Self {
let mut cnt = HashMap::new();
for &x in &nums2 {
*cnt.entry(x).or_insert(0) += 1;
}
Self { nums1, nums2, cnt }
}
fn add(&mut self, index: i32, val: i32) {
let i = index as usize;
let old_val = self.nums2[i];
*self.cnt.entry(old_val).or_insert(0) -= 1;
if self.cnt[&old_val] == 0 {
self.cnt.remove(&old_val);
}
self.nums2[i] += val;
let new_val = self.nums2[i];
*self.cnt.entry(new_val).or_insert(0) += 1;
}
fn count(&self, tot: i32) -> i32 {
let mut ans = 0;
for &x in &self.nums1 {
let target = tot - x;
if let Some(&c) = self.cnt.get(&target) {
ans += c;
}
}
ans
}
}
/**
* Your FindSumPairs object will be instantiated and called as such:
* let mut obj = FindSumPairs::new(nums1, nums2);
* obj.add(index, val);
* let ret_2: i32 = obj.count(tot);
*/
###js
/**
* @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)
*/
###cs
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);
*/
时间复杂度 $O(n \times q)$，空间复杂度 $O(m)$。其中 $n$ 和 $m$ 分别是数组 $\textit{nums1}$ 和 $\textit{nums2}$ 的长度，而 $q$ 是调用 $\text{count}$ 方法的次数。
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~
