“枚举右，维护左”是一个非常经典且高效的算法设计范式。

1. “枚举右，维护左”的思想总结

对于双变量（或多变量）问题，传统的双重循环是同时尝试所有的 $(i, j)$ 组合，时间复杂度通常为 $O(N^2)$。

该技巧的核心在于解开双变量的关联性： 1. 时序无后效性：当我们从左到右遍历数组，指针指向当前的右变量 $a_j$ 时，其左侧的所有元素 $a_i$（其中 $i < j$）均已被处理过。 2. 转换单变量：将关系式变形，把与 $a_j$ 相关的项移到等式右边，把与 $a_i$ 相关的项移到等式左边。 3. 空间换时间：利用哈希表（或其他数据结构）实时维护已经遍历过的左侧元素 $a_i$。在处理 $a_j$ 时，只需在 $O(1)$ 时间内查询哈希表中是否存在满足变形后等式的 $a_i$，查询完毕后，再将当前的 $a_j$ 存入哈希表中作为后续的“左变量”。

2. 常见适用式子与变形

只要关系式可以整理为 “关于 $a_i$ 的表达式 = 关于 $a_j$ 的表达式”，且 $i < j$，就可以使用此技巧。以下是常见的数学与逻辑关系变形：

① 基础加减关系

• 和为定值：$a_i + a_j = t \implies a_i = t - a_j$
  • 查找目标：在哈希表中查找是否存在 $t - a_j$。
• 差为定值（大减小）：$a_j - a_i = t \implies a_i = a_j - t$ （已知 $t$）
  • 查找目标：在哈希表中查找是否存在 $a_j - t$。
• 差为定值（小减大）：$a_i - a_j = t \implies a_i = a_j + t$
  • 查找目标：在哈希表中查找是否存在 $a_j + t$。

② 乘除与乘方关系

• 积为定值：$a_i \cdot a_j = t \implies a_i = t / a_j$ （需满足 $t \pmod {a_j} == 0$）
  • 查找目标：在哈希表中查找是否存在商 $t / a_j$。
• 平方和/差：$a_i^2 + a_j^2 = t \implies a_i^2 = t - a_j^2$
  • 查找目标：在哈希表中查找是否存在值 $t - a_j^2$。

③ 位运算关系

• 异或为定值：$a_i \oplus a_j = t \implies a_i = t \oplus a_j$ （利用异或性质：$x \oplus y = z \iff x = z \oplus y$）
  • 查找目标：在哈希表中查找是否存在 $t \oplus a_j$。

④ 同余与整除关系

• 和能被 $k$ 整除：$(a_i + a_j) \pmod k = 0 \implies a_i \pmod k = (k - a_j \pmod k) \pmod k$
  • 维护内容：哈希表维护历史元素的余数 $a_i \pmod k$ 的出现次数。
  • 查找目标：查找匹配余数的个数。

⑤ 前缀和与子数组问题（最经典的延伸）

• 连续子数组和为 $k$：设 $s[x]$ 为前缀和，子数组和表示为 $s[j] - s[i] = k \implies s[i] = s[j] - k$ （其中 $i < j$，子数组区间为 $[i+1, j]$）
  • 维护内容：哈希表维护历史前缀和 $s[i]$ 出现的次数。
  • 查找目标：在哈希表中查找值为 $s[j] - k$ 的前缀和个数。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com