Kimi LeetCode 3943. 递增后的数对数量 Java实现

这是 LeetCode 3943 递增后的数对数量 的 Java 实现。解题思路本题的核心难点在于支持区间加操作的同时快速查询某个值在数组中的出现次数。关键观察- nums1.length 5极短- nums2.length 5×10⁴queries.length 5×10⁴对于类型 2 查询 [2, tot]答案为\sum{j0}^{|nums1|-1} \text{count}(nums2,\ tot - nums1[j])因此问题转化为维护 nums2 的频次信息支持区间加和单值频次查询。采用 分块Sqrt Decomposition- 将 nums2 分成大小约 \sqrt{n} 的块- 每块维护一个 HashMap 记录块内元素的基础值频次以及一个懒标记 add- 完整块区间加直接 add val- 不完整块先将懒标记下推更新数组和 map再暴力修改- 查询目标值减去该块的 add 后在 map 中查找由于值可能累积到 5 \times 10^9超出 int需用 long 存储。时间复杂度O(q \cdot (\sqrt{n} |nums1| \cdot \sqrt{n}))约为 O(10^8) 级别。javaimport java.util.*;class Solution {private static class Block {int l, r; // 块管辖区间 [l, r)MapLong, Integer cnt; // 基础值的频次不含 addlong add; // 懒标记Block(int l, int r) {this.l l;this.r r;this.cnt new HashMap();this.add 0;}}public int[] numberOfPairs(int[] nums1, int[] nums2, int[][] queries) {int n nums2.length;// 块大小取 sqrt(n)约 220~230int blockSize Math.max(1, (int) Math.sqrt(n));int blockCnt (n blockSize - 1) / blockSize;Block[] blocks new Block[blockCnt];// 用 long 数组存储实际值防止溢出long[] arr new long[n];for (int i 0; i n; i) {arr[i] nums2[i];}// 初始化分块for (int i 0; i blockCnt; i) {int L i * blockSize;int R Math.min(n, L blockSize);blocks[i] new Block(L, R);for (int j L; j R; j) {blocks[i].cnt.merge(arr[j], 1, Integer::sum);}}// 统计类型 2 查询个数int q2 0;for (int[] q : queries) {if (q[0] 2) q2;}int[] ans new int[q2];int idx 0;for (int[] q : queries) {if (q[0] 1) { // 区间加int L q[1], R q[2], val q[3];for (Block b : blocks) {if (b.r L || b.l R) continue; // 无交集if (L b.l b.r R 1) {// 完整块直接打懒标记b.add val;} else {// 不完整块先下推懒标记if (b.add ! 0) {for (int i b.l; i b.r; i) {long oldVal arr[i];long newVal oldVal b.add;// 旧值频次 -1b.cnt.merge(oldVal, -1, (oldV, newV) -oldV newV 0 ? null : oldV newV);// 新值频次 1b.cnt.merge(newVal, 1, Integer::sum);arr[i] newVal;}b.add 0;}// 暴力修改交集部分int start Math.max(L, b.l);int end Math.min(R, b.r - 1);for (int i start; i end; i) {b.cnt.merge(arr[i], -1, (oldV, newV) -oldV newV 0 ? null : oldV newV);arr[i] val;b.cnt.merge(arr[i], 1, Integer::sum);}}}} else { // 类型 2 查询long tot q[1];long res 0;for (Block b : blocks) {for (int x : nums1) {long need tot - x - b.add;res b.cnt.getOrDefault(need, 0);}}ans[idx] (int) res;}}return ans;}}关键点说明1. long 存储add 累积可能超过 int 上限约 5 \times 10^9必须使用 long2. 懒标记下推不完整块修改前先将块内所有元素的实际值更新到 arr并同步 cnt3. 频次为 0 时删除merge 的 remapping 函数返回 null 可自动移除该 key避免 map 膨胀4. 复杂度每次类型 1 操作最多暴力处理 2\sqrt{n} 个元素每次类型 2 查询遍历 \sqrt{n} 个块每块最多查 |nums1| \le 5 个值