What is the main pattern used in Finding Pairs With a Certain Sum?

The primary pattern is array scanning plus hash lookup, leveraging the small size of nums1 against nums2 for efficient counting.

How should I handle multiple add operations efficiently?

Update the hash map by decrementing the old value count and incrementing the new value count to maintain fast count queries.

Why not scan nums2 directly for every count query?

Scanning nums2 repeatedly is inefficient because it is large. Using a hash map reduces the query time to O(n) where n is nums1 length.

Does the order of nums1 or nums2 matter?

No, the order does not matter since pairs are counted based on value sums, not indices, and hash maps track frequencies.

Can this approach handle large integers in nums1 or nums2?

Yes, the approach uses hash maps to store counts, so it can handle large integer values as long as they are within constraints.

#1865

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

找出和为指定值的下标对

给你两个整数数组 nums1 和 nums2 ，请你实现一个支持下述两类查询的数据结构：累加，将一个正整数加到 nums2 中指定下标对应元素上。计数，统计满足 nums1[i] + nums2[j] 等于指定值的下标对 (i, j) 数目（ 0 且 0 ）。实现 FindSumPairs…

数组哈希表设计

题目描述

给你两个整数数组 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 次

lightbulb

解题思路

方法一：哈希表

我们注意到，数组 $\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}$ 方法的次数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

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)

speed

复杂度分析

指标	值
时间	O(n + m + q_1 + q_2 \cdot n)
空间	O(n + m)

psychology

面试官常问的追问

外企场景

question_mark
Are you leveraging the fact that nums1 is smaller than nums2 to optimize count queries?
question_mark
Can you maintain counts in a hash map without recomputing all pairs after each add?
question_mark
How would your approach change if nums2 was updated frequently and nums1 was very large?

warning

常见陷阱

外企场景

error
Recomputing all pairs on every count query instead of using the hash map for efficient lookup.
error
Failing to update the hash map correctly when adding values to nums2, leading to incorrect counts.
error
Ignoring integer overflow or assuming nums1 and nums2 have similar lengths, reducing efficiency.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow both nums1 and nums2 to be updated dynamically, requiring two hash maps.
arrow_right_alt
Count pairs within a single array instead of between two arrays, changing the scanning logic.
arrow_right_alt
Support finding pairs that satisfy a product or difference condition instead of sum, altering the complement calculation.

help

常见问题

外企场景

继续练习

#1912 设计电影租借系统 #1993 树上的操作 #2013 检测正方形