2026-09-04：递增后的数对数量。用go语言，给定两个整数数组，分别记为第一个数组和第二个数组。同时给出一系列操作，每个操作有两种形式

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：查询数对数量

形式为[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 ans

 if __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助力您的未来发展。