2026-09-04：递增后的数对数量。用go语言，给定两个整数数组，分别记为第一个数组和第二个数组。同时给出一系列操作，每个操作有两种形式：
• 第一种操作会指定一个连续区间（由起始索引和结束索引界定）和一个增量数值，该操作会将第二个数组中该区间内的所有元素统一增加这个增量。
• 第二种操作会给出一个目标总和值，需要统计所有可能的数对，其中第一个数来自第一个数组，第二个数来自第二个数组，且这两个数的和恰好等于该目标值。
所有操作按顺序执行，对于每个第二种操作，记录其统计结果，最终将这些结果按顺序组成一个数组返回。注意操作编号和数组索引均从给定规则出发，但计数时需考虑操作执行后的数组当前状态。
1 <= nums1.length <= 5
1 <= nums2.length <= 50000
1 <= nums1[i], nums2[i] <= 100000
1 <= queries.length <= 50000
queries[i].length == 2 or 4
queries[i] == [1, x, y, val]，或
queries[i] == [2, tot]
0 <= x <= y < nums2.length
1 <= val <= 100000
1 <= tot <= 100000
输入： nums1 = [1,2], nums2 = [3,4], queries = [[2,5],[1,0,0,2],[2,5]]。
输出： [2,1]。
解释：
queries[0] = [2, 5]：有效数对为 nums1[0] + nums2[1] = 1 + 4 = 5 和 nums1[1] + nums2[0] = 2 + 3 = 5。
queries[1] = [1, 0, 0, 2]：将 nums2[0] 增加 2，得到 nums2 = [5, 4]。
queries[2] = [2, 5]：有效数对为 nums1[0] + nums2[1] = 1 + 4 = 5。
因此，answer = [2, 1]。
题目来自力扣3943。
一、整体思想
• 将第二个数组
nums2分成若干连续的“块”，每块大小约为sqrt( len(nums1) * len(nums2) )。因为nums1长度很小（最多5），所以块大小近似为sqrt(len(nums2))。• 每个块维护两个关键信息：
• 一个哈希表（字典）
cnt，记录该块内当前实际值（未经整体偏移）的各数值出现次数；• 一个整数
add，表示该块整体被统一增加的值，这个偏移量不会直接修改cnt中的键，而是在查询时动态考虑。
• 区间加操作时，如果整个块都被区间覆盖，只需修改
add；若只有部分覆盖，则暴力更新该块内被覆盖的元素，同时同步调整cnt。• 查询时，遍历每个块，对于块内每个元素，其实际值为
存储值 + add，所以对于给定目标tot，我们需要在块内找满足x + (实际值) == tot的数量，即实际值 == tot - x，但实际值 =原存储值 + add，所以等价于找原存储值 == tot - x - add，直接从cnt中查找该键的计数即可。
1. 读取输入的两个数组
nums1（长度 m）和nums2（长度 n）。2. 计算分块大小
B = floor( sqrt( m * n ) )，至少为 1。3. 将
nums2按顺序分割成若干块，每块至多B个元素，最后一块可能不足B。记录每块的左边界l和右边界r（左闭右开区间，即包含l不包含r）。4. 对每个块，遍历其区间内的所有元素，构建哈希表
cnt，键为元素值，值为该值在块内出现的次数。同时将每块的add初始化为 0。
查询按照输入顺序依次执行，每个查询可能是两种类型之一，处理方式不同。
类型 1：区间增量更新
形式为[1, x, y, val]，表示将nums2[x..y]中所有元素增加val。
处理步骤：
• 将闭区间转换为左闭右开区间：
l = x，r = y + 1。• 按顺序遍历所有块（块已经按位置排序）：
• 如果当前块的右边界
b.r小于等于l，说明该块完全在区间左侧，跳过。• 如果当前块的左边界
b.l大于等于r，说明该块完全在区间右侧，且由于块顺序，后续块更靠右，因此可以提前结束遍历。• 如果当前块完全被区间覆盖（即
l <= b.l且b.r <= r），则只需将该块的add增加val，表示整块所有元素都加上该增量，无需修改块内哈希表。• 否则，当前块与区间有部分重叠。此时需要对该块内被区间覆盖的那一段元素进行单独修改：
• 确定重叠区间
[bl, br)，其中bl = max(b.l, l)，br = min(b.r, r)。• 遍历该重叠区间内的索引
j（从bl到br-1）：• 获取当前位置的实际存储值（即
nums2[j]，它可能已经因之前的暴力更新而改变）。• 在块哈希表
b.cnt中，将该旧值的计数减 1（若减到 0 则删除该键，以防止计数为 0 的键残留）。• 将
nums2[j]本身增加val。• 将更新后的新值在
b.cnt中的计数加 1。
• 注意：这里不修改该块的
add，因为只有部分元素被单独修改，而add只用于整个块统一偏移。
形式为[2, tot]，需要统计nums1中每个元素与nums2当前实际值之和等于tot的数对数量。
处理步骤：
• 初始化结果
res = 0。• 遍历所有块：
• 对于当前块
b，其所有元素的实际值都隐式地包含一个整体偏移b.add。因此，对于nums1中的每一个x，我们希望找到块内是否存在某个存储值v，使得x + (v + b.add) == tot，即v == tot - x - b.add。• 从块哈希表
b.cnt中查询键为tot - x - b.add的出现次数，累加到res中。
• 将
res追加到答案数组answer中。
以题目给出的示例nums1 = [1,2]，nums2 = [3,4]，操作序列为[[2,5], [1,0,0,2], [2,5]]：
1. 初始化：m=2, n=2, B = sqrt(4)=2，因此整个
nums2作为一个块（左边界0，右边界2），cnt = {3:1, 4:1}，add=0。2. 第一个查询
[2,5]：遍历块，b.add=0，计算tot=5。
• 对于 x=1：目标存储值为 5-1-0=4，
cnt[4]=1，累加1。• 对于 x=2：目标存储值为 5-2-0=3，
cnt[3]=1，累加1。res=2，输出第一个结果 2。
3. 第二个查询[1,0,0,2]：区间[0,0]（即索引0），l=0, r=1。
• 当前块完全覆盖（因为块区间[0,2)包含[0,1)），所以直接
b.add += 2，add变为2，不修改cnt。
4. 第三个查询[2,5]：遍历块，b.add=2。
• 对于 x=1：目标存储值 = 5-1-2=2，
cnt[2]不存在，计数0。• 对于 x=2：目标存储值 = 5-2-2=1，
cnt[1]不存在，计数0。
但实际数组nums2现在应为[5,4]，因为索引0增加了2（实际值为3+2=5），索引1仍为4。有效数对：1+4=5和2+?，只有1+4满足，所以结果应为1。但我们的计算似乎没有得到1？
检查：我们计算时，对于 x=1，目标存储值应为tot - x - add = 5-1-2=2，但cnt里存储的是原始值（未加偏移），现在原始值分别是3和4，cnt仍为 {3:1,4:1}，没有2，所以没计数。但实际有效数对是nums1[0] + nums2[1] = 1 + 4 = 5，其中4是未偏移的值，但此时块整体偏移 add=2，意味着块内所有存储值实际都增加了2，但只有索引0被增加了（因为区间加仅作用于索引0），然而我们的整体偏移add却应用于整个块，这显然错误！
这里暴露出代码的问题：当块部分更新时，我们的处理方式是将特定元素单独修改并更新cnt，但整体偏移add仍然保留。在这个示例中，最初整个块作为一个块，后来对索引0单独增加2，我们本应暴力更新该元素，但由于块完全覆盖？等等，区间 [0,0] 并不完全覆盖整个块 [0,2)，因为我们的条件l <= b.l && b.r <= r要求l=0, r=1，而 b.l=0, b.r=2，不满足 b.r <= r（2 <= 1 为假），所以进入部分覆盖分支，应该进行暴力更新。但代码中却是整块覆盖？我们重新看代码逻辑：在遍历块时，首先判断if b.r <= l { continue }，如果b.r <= l则跳过；然后判断if b.l >= r { break }；接着判断if l <= b.l && b.r <= r是否为真。对于 l=0, r=1, b.l=0, b.r=2：l <= b.l(0<=0) 为真，b.r <= r(2<=1) 为假，所以不满足整块覆盖，进入部分覆盖。所以会执行暴力更新循环，更新索引0的元素。所以实际过程是：将旧值3从cnt中减1，nums2[0]加2变为5，cnt[5]加1，此时cnt变为{4:1,5:1}，add仍为0。所以第三个查询时，add=0，那么对于x=1，目标存储值=5-1-0=4，cnt[4]=1，得到1；对于x=2，目标=3，cnt[3]=0，总res=1。结果正确。
因此，我们的描述需要强调：只有当整块被完全覆盖时，才会修改add；部分覆盖时，会直接修改实际数组值和cnt，但add保持不变。所以示例中部分覆盖会触发暴力更新，而不是整体加add。
设m = len(nums1)，n = len(nums2)，操作总数为Q。
•初始化：遍历
nums2一次，构建各块的哈希表，时间复杂度为O(n)。•区间加操作（类型1）：
• 遍历所有块，块数为
O(n/B)。• 对于完全覆盖的块，只进行常数时间更新
add。• 对于部分覆盖的块，最多两个边界块需要暴力更新，每个边界块大小至多
B，所以暴力更新总代价为O(B)。• 因此单次区间加的时间复杂度为
O(n/B + B)。
•查询操作（类型2）：
• 遍历所有块，块数为
O(n/B)。• 对每个块，需要遍历
nums1的所有元素（共m个），并对每个元素进行一次哈希表查找，所以每个块代价为O(m)。• 单次查询时间复杂度为
O(m * n/B)。
• 由于块大小
B = floor( sqrt(m * n) )，代入得到：• 区间加：
O(n/B + B) = O( n / sqrt(mn) + sqrt(mn) ) = O( sqrt(n/m) + sqrt(mn) )。因为m很小（≤5），可近似为O( sqrt(n) )。• 查询：
O(m * n/B) = O( m * n / sqrt(mn) ) = O( m * sqrt(n/m) ) = O( sqrt(m) * sqrt(n) )，同样由于m小，近似为O( sqrt(n) )。
• 因此，总时间复杂度为
O( Q * sqrt(n) )（忽略常数因子和小的 m 影响）。在最坏情况下n=50000，Q=50000，开根号约 224，总操作约 1.1e7，可以接受。
• 存储
nums2自身：输入数组本身，不计入额外空间。• 存储分块结构：每个块需要记录左右边界（常数）、一个哈希表
cnt。所有块的cnt中总共存储了n个键值对（每个元素在所属块中出现一次，计数聚合），因此哈希表的总空间为O(n)。• 块结构数组大小为
O(n/B)，远小于n，忽略不计。• 答案数组
ans最多存储查询次数，即O(Q)，但通常不算作额外空间（或计入输出），若严格考虑额外空间可算作O(Q)。• 其他临时变量常数。
因此，总的额外空间复杂度为O(n)（若不计答案数组，则主要为O(n)；若计入答案数组，则为O(n + Q)，但 Q 与 n 同量级，仍可视为O(n)级别）。
Go完整代码如下：
package main
import (
"fmt"
"math"
)
func numberOfPairs(nums1, nums2 []int, queries [][]int) (ans []int) {
m, n := len(nums1), len(nums2)
B := int(math.Sqrt(float64(m * n)))
type block struct {
l, r int // 这一段对应 nums2 的子数组 [l, r)，注意是左闭右开区间
cnt map[int]int // 这一段每个元素的出现次数
add int // 这一段整体要增加 add
}
blocks := make([]block, (n-1)/B+1)
for i := 0; i < n; i += B {
r := min(i+B, n)
cnt := map[int]int{}
for _, x := range nums2[i:r] {
cnt[x]++
}
blocks[i/B] = block{i, r, cnt, 0}
}
for _, q := range queries {
if q[0] == 1 {
l, r, val := q[1], q[2]+1, q[3]
for i := range blocks {
b := &blocks[i]
if b.r <= l {
continue
}
if b.l >= r {
break
}
// b 在 [l, r) 中
if l <= b.l && b.r <= r {
b.add += val
continue
}
// b 的一部分在 [l, r) 中
bl := max(b.l, l)
br := min(b.r, r)
// 暴力更新 nums2 的子数组 [bl, br) 的元素值及其出现次数
for j := bl; j < br; j++ {
b.cnt[nums2[j]]-- // 撤销旧的
nums2[j] += val
b.cnt[nums2[j]]++ // 添加新的
}
}
} else {
res := 0
for _, b := range blocks {
target := q[1] - b.add
for _, x := range nums1 {
res += b.cnt[target-x]
}
}
ans = append(ans, res)
}
}
return
}func main() {
nums1 := []int{1, 2}
nums2 := []int{3, 4}
queries := [][]int{{2, 5}, {1, 0, 0, 2}, {2, 5}}
result := numberOfPairs(nums1, nums2, queries)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
from typing import List
def numberOfPairs(nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
m, n = len(nums1), len(nums2)
B = int((m * n) ** 0.5)
if B == 0:
B = 1
# 分块结构：每个块记录左右边界、元素计数字典、整体懒标记
blocks = []
for start in range(0, n, B):
end = min(start + B, n)
cnt = {}
for x in nums2[start:end]:
cnt[x] = cnt.get(x, 0) + 1
blocks.append({
'l': start,
'r': end,
'cnt': cnt,
'add': 0
})
ans = []
for q in queries:
if q[0] == 1:
l, r, val = q[1], q[2] + 1, q[3] # 区间为左闭右开 [l, r)
for b in blocks:
if b['r'] <= l:
continue
if b['l'] >= r:
break
# 整个块被区间覆盖
if l <= b['l'] and b['r'] <= r:
b['add'] += val
else:
# 部分覆盖，暴力更新元素
bl = max(b['l'], l)
br = min(b['r'], r)
for j in range(bl, br):
old = nums2[j]
# 移除旧值计数
b['cnt'][old] -= 1
if b['cnt'][old] == 0:
del b['cnt'][old]
new = old + val
nums2[j] = new
b['cnt'][new] = b['cnt'].get(new, 0) + 1
else:
tot = q[1]
res = 0
for b in blocks:
target = tot - b['add'] # 考虑块整体偏移后的实际目标值
for x in nums1:
res += b['cnt'].get(target - x, 0)
ans.append(res)
return ansif __name__ == "__main__":
nums1 = [1, 2]
nums2 = [3, 4]
queries = [[2, 5], [1, 0, 0, 2], [2, 5]]
print(numberOfPairs(nums1, nums2, queries))
C++完整代码如下：
using namespace std;vector numberOfPairs(vector& nums1, vector& nums2, vector int >>& queries) {
int m = nums1.size(), n = nums2.size();
int B = ( int )sqrt((double)m * n);
if (B == 0 ) B = 1 ; // 防止除零
// 块结构
struct Block {
int l, r; // 左闭右开区间 [l, r)
unordered_map< int , int > cnt; // 每个元素的出现次数
int add; // 整块增加量
};
vector blocks;
for ( int i = 0 ; i < n; i += B) {
int r = min(i + B, n);
unordered_map< int , int > cnt;
for ( int j = i; j < r; ++j) {
cnt[nums2[j]]++;
}
blocks.push_back({i, r, cnt, 0 });
}
vector< int > ans;
for ( const auto& q : queries) {
if (q[ 0 ] == 1 ) {
int l = q[ 1 ];
int r = q[ 2 ] + 1 ; // 转化为左闭右开
int val = q[ 3 ];
for (auto& b : blocks) {
if (b.r <= l) continue ;
if (b.l >= r) break ;
// 整块都在区间内
if (l <= b.l && b.r <= r) {
b.add += val;
continue ;
}
// 部分覆盖，暴力更新
int bl = max(b.l, l);
int br = min(b.r, r);
for ( int j = bl; j < br; ++j) {
// 删除旧值
int old = nums2[j];
auto it = b.cnt.find(old);
if (it != b.cnt.end()) {
it->second--;
if (it->second == 0 ) {
b.cnt.erase(it); // 可选，避免保留零值
}
}
// 更新实际数组
nums2[j] = old + val;
// 添加新值
b.cnt[nums2[j]]++;
}
}
} else { // 类型 2
int tot = q[ 1 ];
int res = 0 ;
for ( const auto& b : blocks) {
int target = tot - b.add;
for ( int x : nums1) {
auto it = b.cnt.find(target - x);
if (it != b.cnt.end()) {
res += it->second;
}
}
}
ans.push_back(res);
}
}
return ans;
}
int main() {
vector< int > nums1 = { 1 , 2 };
vector< int > nums2 = { 3 , 4 };
vector int >> queries = {{ 2 , 5 }, { 1 , 0 , 0 , 2 }, { 2 , 5 }};
vector< int > result = numberOfPairs(nums1, nums2, queries);
for ( int v : result) {
cout << v << " " ;
}
cout << endl;
return 0 ;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
热门跟贴