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

1. 枚举中间变量高效解决三元组问题的通用思路在算法竞赛和日常刷题中我们经常会遇到需要统计满足特定条件的三元组i,j,k的问题。这类问题如果采用暴力枚举所有可能的三元组时间复杂度通常高达O(n³)在数据量稍大时就会超时。今天我要分享的是一种高效解决这类问题的通用思路——枚举中间变量法。1.1 为什么选择中间变量作为突破口当我们面对三元组问题时最直观的想法可能是固定i和j然后枚举k或者固定i和k然后枚举j。但这种思路往往难以优化时间复杂度。而选择固定中间的j将问题分解为左右两部分独立处理可以带来几个显著优势解耦依赖关系将原本相互关联的三元关系拆分为两个独立的二元关系i与j的关系j与k的关系预处理可能性可以预先计算并存储右侧的信息在遍历时只需维护左侧信息降低复杂度通常能将时间复杂度从O(n³)降低到O(n²)甚至O(n)1.2 基本框架与实现步骤基于枚举中间变量的解法通常遵循以下框架预处理右侧信息根据问题需求预先计算并存储每个位置右侧的相关数据如出现次数、最大值等遍历数组维护左侧信息从左到右遍历时动态维护当前位置左侧的相关数据合并左右结果在遍历到每个位置j时将左侧和右侧的信息按照题目要求进行组合计算这种方法的精妙之处在于它通过固定中间变量将原本需要同时考虑三个变量的复杂问题分解为两个可以独立处理的子问题。2. 典型例题解析从一维数组到二维平面2.1 统计特殊三元组LeetCode 35832.1.1 问题描述给定一个整数数组nums统计满足nums[i] * 2 nums[j] * 2 nums[k] * 2的三元组(i,j,k)的数量其中i j k。2.1.2 解题思路按照枚举中间变量的思路固定中间的j统计j左侧满足nums[i] nums[j] * 2的元素个数统计j右侧满足nums[k] nums[j] * 2的元素个数根据乘法原理将左右两侧的计数相乘并累加2.1.3 实现细节与优化class Solution { public int specialTriplets(int[] nums) { final int MOD 1_000_000_007; MapInteger,Integer suf new HashMap(); // 预处理统计所有元素出现的次数初始时代表右侧所有元素 for(int x : nums){ suf.merge(x,1,Integer::sum); } long ans 0; MapInteger,Integer pre new HashMap(); for(int x : nums){ // 当前x作为j先从右侧统计中移除因为右侧应该是j1到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 31282.2.1 问题描述给定一个m×n的二进制矩阵grid统计其中以1为顶点形成的直角三角形的数量。直角三角形的定义是三个顶点均为1且两条直角边分别平行于矩阵的行和列。2.2.2 解题思路将直角顶点视为中间变量预处理每行和每列的1的个数对于每个grid[i][j] 1的位置同一行有rowSum[i]个1包括自己同一列有colSum[j]个1包括自己根据乘法原理该点作为直角顶点的三角形数量为(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 28742.3.1 问题描述给定整数数组nums找到最大值(nums[i]-nums[j])*nums[k]其中i j k。2.3.2 解题思路固定中间的j预处理右侧最大值数组maxSuf其中maxSuf[i]表示从i到n-1的最大值遍历时维护左侧最大值maxPre对于每个j计算(maxPre - nums[j]) * maxSuf[j1]并更新全局最大值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]); // 计算以i1为j时的可能最大值 long current (long)(maxPre - nums[i1]) * maxSuf[i2]; ans Math.max(ans, current); } return ans 0 ? 0 : ans; } }边界处理注意数组越界问题特别是在处理i2时。另外当结果为负时需要返回0。2.4 回旋镖数量LeetCode 4472.4.1 问题描述给定平面上n个不同的点统计满足距离相等的三元组(i,j,k)的数量其中i,j,k互不相同且j到i的距离等于j到k的距离。2.4.2 解题思路将问题转化为以每个点作为中心点j统计其他点到j的距离相同的点对数量外层循环枚举中心点j内层循环计算所有其他点到j的距离使用哈希表统计每个距离出现的次数对于出现c次的相同距离有c*(c-1)种排列方式2.4.3 代码实现class Solution { public int numberOfBoomerangs(int[][] points) { int ans 0; for(int[] p1 : points) { MapInteger,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 适用场景判断枚举中间变量的方法特别适用于以下特征的问题涉及三个变量或三个维度的关系变量之间存在顺序或位置关系如ijk可以将条件分解为左侧和右侧两个独立部分可以通过预处理优化右侧信息的获取3.2 常见变体与应对策略3.2.1 不同数据结构的应用数组/链表通常使用前后缀数组或哈希表来维护左右信息矩阵/二维平面可能需要同时维护行和列的信息字符串可能需要统计字符出现频率或维护滑动窗口3.2.2 条件变化的处理等式条件如nums[i] nums[j] * 2可以使用哈希表直接查找不等式条件如nums[i] nums[j]可能需要维护有序数据结构距离/相似度条件可能需要自定义比较函数或距离计算3.3 性能优化技巧空间优化有时可以用变量代替数组如只维护当前最大值而非整个前缀数组遍历顺序优化根据问题特点选择合适的遍历方向从左到右或从右到左数据结构选择根据操作频率选择合适的数据结构哈希表、数组、优先队列等提前终止在某些情况下可以提前结束循环以减少不必要的计算4. 常见错误与调试技巧4.1 边界条件处理数组越界特别是在处理i-1或i1时要确保索引有效空输入考虑输入为空数组或空矩阵的情况最小值/最大值注意整型溢出问题必要时使用long类型4.2 逻辑错误排查前后缀更新时机确保在正确的时间点更新前后缀信息乘法原理应用确认左右两侧的计数是否独立且正确中间变量选择验证选择的中间变量是否能有效解耦问题4.3 调试建议小规模测试先用小例子手动验证算法正确性打印中间结果在关键步骤输出变量值以验证逻辑对比暴力解法对于小规模数据与暴力解法结果对比验证在实际刷题过程中我发现这类问题的难点往往不在于算法本身而在于如何准确识别问题特征并选择合适的中间变量。通过大量练习培养这种模式识别能力可以显著提高解题效率。