1. 枚举中间变量：高效解决三元组问题的通用思路

在算法竞赛和日常刷题中，我们经常会遇到需要统计满足特定条件的三元组（i,j,k）的问题。这类问题如果采用暴力枚举所有可能的三元组，时间复杂度通常高达O(n³)，在数据量稍大时就会超时。今天我要分享的是一种高效解决这类问题的通用思路——枚举中间变量法。

1.1 为什么选择中间变量作为突破口？

当我们面对三元组问题时，最直观的想法可能是固定i和j，然后枚举k，或者固定i和k，然后枚举j。但这种思路往往难以优化时间复杂度。而选择固定中间的j，将问题分解为左右两部分独立处理，可以带来几个显著优势：

1. 解耦依赖关系：将原本相互关联的三元关系拆分为两个独立的二元关系（i与j的关系，j与k的关系）
2. 预处理可能性：可以预先计算并存储右侧的信息，在遍历时只需维护左侧信息
3. 降低复杂度：通常能将时间复杂度从O(n³)降低到O(n²)甚至O(n)

1.2 基本框架与实现步骤

基于枚举中间变量的解法通常遵循以下框架：

1. 预处理右侧信息：根据问题需求，预先计算并存储每个位置右侧的相关数据（如出现次数、最大值等）
2. 遍历数组维护左侧信息：从左到右遍历时，动态维护当前位置左侧的相关数据
3. 合并左右结果：在遍历到每个位置j时，将左侧和右侧的信息按照题目要求进行组合计算

这种方法的精妙之处在于，它通过固定中间变量，将原本需要同时考虑三个变量的复杂问题，分解为两个可以独立处理的子问题。

2. 典型例题解析：从一维数组到二维平面

2.1 统计特殊三元组（LeetCode 3583）

2.1.1 问题描述

给定一个整数数组nums，统计满足nums[i] * 2 == nums[j] * 2 == nums[k] * 2的三元组(i,j,k)的数量，其中i < j < k。

2.1.2 解题思路

按照枚举中间变量的思路：

1. 固定中间的j
2. 统计j左侧满足nums[i] == nums[j] * 2的元素个数
3. 统计j右侧满足nums[k] == nums[j] * 2的元素个数
4. 根据乘法原理，将左右两侧的计数相乘并累加

2.1.3 实现细节与优化

class Solution { public int specialTriplets(int[] nums) { final int MOD = 1_000_000_007; Map<Integer,Integer> suf = new HashMap<>(); // 预处理：统计所有元素出现的次数（初始时代表右侧所有元素） for(int x : nums){ suf.merge(x,1,Integer::sum); } long ans = 0; Map<Integer,Integer> pre = new HashMap<>(); for(int x : nums){ // 当前x作为j，先从右侧统计中移除（因为右侧应该是j+1到n-1） suf.merge(x, -1, Integer::sum); // 计算左侧满足条件的i的个数 * 右侧满足条件的k的个数 ans += (long)pre.getOrDefault(x*2,0) * suf.getOrDefault(x*2,0); // 将当前元素加入左侧统计（为下一个j做准备） pre.merge(x,1,Integer::sum); } return (int)(ans % MOD); } }

关键技巧：使用两个哈希表分别维护左侧和右侧的元素出现次数。遍历时动态更新这两个哈希表，确保它们始终反映正确的前后区间信息。

2.2 直角三角形计数（LeetCode 3128）

2.2.1 问题描述

给定一个m×n的二进制矩阵grid，统计其中以1为顶点形成的直角三角形的数量。直角三角形的定义是：三个顶点均为1，且两条直角边分别平行于矩阵的行和列。

2.2.2 解题思路

将直角顶点视为中间变量：

1. 预处理每行和每列的1的个数
2. 对于每个grid[i][j] == 1的位置：
   • 同一行有rowSum[i]个1（包括自己）
   • 同一列有colSum[j]个1（包括自己）
3. 根据乘法原理，该点作为直角顶点的三角形数量为(rowSum[i]-1)*(colSum[j]-1)

2.2.3 代码实现

class Solution { public long numberOfRightTriangles(int[][] grid) { int n = grid[0].length; int[] colSum = new int[n]; // 预处理：统计每列的1的个数 for(int[] row : grid){ for(int i = 0; i < row.length; i++){ colSum[i] += row[i]; } } long ans = 0; for(int[] row : grid){ int rowSum = 0; // 统计当前行的1的个数 for(int r : row){ rowSum += r; } // 遍历当前行的每个元素 for(int i = 0; i < row.length; i++){ if(row[i] == 1){ ans += (long)(colSum[i]-1) * (rowSum-1); } } } return ans; } }

性能优化：通过一次遍历同时统计行和列的1的个数，避免了额外的遍历开销。注意在计算时减去当前点自身的计数。

2.3 有序三元组最大值（LeetCode 2874）

2.3.1 问题描述

给定整数数组nums，找到最大值(nums[i]-nums[j])*nums[k]，其中i < j < k。

2.3.2 解题思路

固定中间的j：

1. 预处理右侧最大值数组maxSuf，其中maxSuf[i]表示从i到n-1的最大值
2. 遍历时维护左侧最大值maxPre
3. 对于每个j，计算(maxPre - nums[j]) * maxSuf[j+1]，并更新全局最大值

2.3.3 实现代码

class Solution { public long maximumTripletValue(int[] nums) { int n = nums.length; int[] maxSuf = new int[n]; // 预处理：计算每个位置右侧的最大值 int mx = Integer.MIN_VALUE; for(int i = n-1; i >=0; i--) { mx = Math.max(mx, nums[i]); maxSuf[i] = mx; } long ans = 0; int maxPre = Integer.MIN_VALUE; for(int i = 0; i < n - 1; i++) { maxPre = Math.max(maxPre, nums[i]); // 计算以i+1为j时的可能最大值 long current = (long)(maxPre - nums[i+1]) * maxSuf[i+2]; ans = Math.max(ans, current); } return ans < 0 ? 0 : ans; } }

边界处理：注意数组越界问题，特别是在处理i+2时。另外，当结果为负时需要返回0。

2.4 回旋镖数量（LeetCode 447）

2.4.1 问题描述

给定平面上n个不同的点，统计满足距离相等的三元组(i,j,k)的数量，其中i,j,k互不相同且j到i的距离等于j到k的距离。

2.4.2 解题思路

将问题转化为以每个点作为中心点j，统计其他点到j的距离相同的点对数量：

1. 外层循环枚举中心点j
2. 内层循环计算所有其他点到j的距离
3. 使用哈希表统计每个距离出现的次数
4. 对于出现c次的相同距离，有c*(c-1)种排列方式

2.4.3 代码实现

class Solution { public int numberOfBoomerangs(int[][] points) { int ans = 0; for(int[] p1 : points) { Map<Integer,Integer> cnt = new HashMap<>(); for(int[] p2 : points) { // 计算距离的平方（避免浮点数精度问题） int dx = p1[0] - p2[0]; int dy = p1[1] - p2[1]; int dis = dx*dx + dy*dy; // 更新该距离的出现次数 cnt.put(dis, cnt.getOrDefault(dis, 0) + 1); } // 统计当前中心点的贡献 for(int c : cnt.values()) { ans += c * (c - 1); } } return ans; } }

距离计算技巧：直接使用距离的平方进行比较，避免了开方运算和浮点数精度问题。注意这里不需要实际计算距离值，只需要保证比较的值是唯一的即可。

3. 模式识别与解题技巧

3.1 适用场景判断

枚举中间变量的方法特别适用于以下特征的问题：

1. 涉及三个变量或三个维度的关系
2. 变量之间存在顺序或位置关系（如i<j<k）
3. 可以将条件分解为左侧和右侧两个独立部分
4. 可以通过预处理优化右侧信息的获取

3.2 常见变体与应对策略

3.2.1 不同数据结构的应用

1. 数组/链表：通常使用前后缀数组或哈希表来维护左右信息
2. 矩阵/二维平面：可能需要同时维护行和列的信息
3. 字符串：可能需要统计字符出现频率或维护滑动窗口

3.2.2 条件变化的处理

1. 等式条件：如nums[i] == nums[j] * 2，可以使用哈希表直接查找
2. 不等式条件：如nums[i] < nums[j]，可能需要维护有序数据结构
3. 距离/相似度条件：可能需要自定义比较函数或距离计算

3.3 性能优化技巧

1. 空间优化：有时可以用变量代替数组，如只维护当前最大值而非整个前缀数组
2. 遍历顺序优化：根据问题特点选择合适的遍历方向（从左到右或从右到左）
3. 数据结构选择：根据操作频率选择合适的数据结构（哈希表、数组、优先队列等）
4. 提前终止：在某些情况下可以提前结束循环以减少不必要的计算

4. 常见错误与调试技巧

4.1 边界条件处理

1. 数组越界：特别是在处理i-1或i+1时，要确保索引有效
2. 空输入：考虑输入为空数组或空矩阵的情况
3. 最小值/最大值：注意整型溢出问题，必要时使用long类型

4.2 逻辑错误排查

1. 前后缀更新时机：确保在正确的时间点更新前后缀信息
2. 乘法原理应用：确认左右两侧的计数是否独立且正确
3. 中间变量选择：验证选择的中间变量是否能有效解耦问题

4.3 调试建议

1. 小规模测试：先用小例子手动验证算法正确性
2. 打印中间结果：在关键步骤输出变量值以验证逻辑
3. 对比暴力解法：对于小规模数据，与暴力解法结果对比验证

在实际刷题过程中，我发现这类问题的难点往往不在于算法本身，而在于如何准确识别问题特征并选择合适的中间变量。通过大量练习培养这种模式识别能力，可以显著提高解题效率。