【算法文章 7 | 枚举中间维护两边的题解总结】

在刷 LeetCode 的过程中，我们经常会遇到要求统计“满足某种条件的三元组个数”的问题。这类问题如果暴力枚举，复杂度通常是 $O(n^3)$，往往会超时。但如果我们变换视角，采用**“枚举中间变量”**的思想，往往能将复杂度降至 $O(n)$ 或 $O(n^2)$。

连续看几个题，我们就可以快速掌握这种题型的基本方法：

3583. 统计特殊三元组

题目链接：https://leetcode.cn/problems/count-special-triplets/

思路

代码

class Solution {
private static int MOD = 1_000_000_007;
public int specialTriplets(int[] nums) {

int n = nums.length;
//统计后缀
Map<Integer,Integer> sufSum = new HashMap<>();
for(int i = 1; i < n; i++) {
sufSum.merge(nums[i], 1, Integer::sum);
}
//统计前缀
Map<Integer,Integer> preSum = new HashMap<>();

long ans = 0;
//遍历数组
for(int j = 1; j < n–1; j++) {
//后缀去掉当前的数
sufSum.merge(nums[j], –1, Integer::sum);
//前缀加上当前的数
preSum.merge(nums[j–1], 1, Integer::sum);
//更新
ans += (long)preSum.getOrDefault(nums[j]*2,0) * sufSum.getOrDefault(nums[j]*2,0);

}
return (int)(ans % MOD);
}
}

贴一个另一种写法

class Solution {
public int specialTriplets(int[] nums) {
//左边出现的次数可以一边遍历一边统计
//右边：先统计整个数组，然后遍历数组，撤销[0,j]中统计的元素出现次数
final int MOD = 1_000_000_007;
Map<Integer,Integer> suf = new HashMap<>();
for(int x : nums){//右边的：遍历统计所有
suf.merge(x,1,Integer::sum);
//suf.put(x,suf.getOrDefault(x,0)+1);
}
long ans = 0;
Map<Integer,Integer> pre = new HashMap<>();
for(int x : nums){//开始遍历nums[j]
suf.merge(x, –1, Integer::sum); // suf[x]– // 撤销
ans += (long)pre.getOrDefault(x*2,0) * suf.getOrDefault(x*2,0);
pre.merge(x,1,Integer::sum);
//pre.put(x,pre.getOrDefault(x,0)+1);
}
return (int)(ans % MOD);

}
}

3128. 直角三角形

题目链接：https://leetcode.cn/problems/right-triangles/

思路

代码

class Solution {
public long numberOfRightTriangles(int[][] grid) {
int m = grid.length;
int n = grid[0].length;

int[] rowSum = new int[m];
int[] colSum = new int[n];

// 一次遍历同时统计行和列的 1 的个数
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
rowSum[i]++;
colSum[j]++;
}
}
}

long ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
ans += (long)(rowSum[i] – 1) * (colSum[j] – 1);
}
}
}
return ans;
}
}

贴一个优化空间的方法：统计每一行的1的个数跟更新答案的时候写在一起

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;
}
}

2874. 有序三元组中的最大值 II

题目链接：https://leetcode.cn/problems/maximum-value-of-an-ordered-triplet-ii/

思路

代码

class Solution {
public long maximumTripletValue(int[] nums) {
long ans = Integer.MIN_VALUE;

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] = Math.max(mx, nums[i]);
}
int maxPre = Integer.MIN_VALUE;
for(int i = 0; i < n – 1; i++) {
maxPre = Math.max(maxPre, nums[i]);
//此时的值是i，所以最大值应该找[i+1,n]
long s = (long)(maxPre – nums[i])*maxSuf[i+1];
ans = Math.max(ans, s);
}
return ans <0 ? 0 : ans;
}
}

贴一个枚举k的写法：

枚举 k，我们需要知道 k 左边 nums[i]−nums[j] 的最大值。

class Solution {
public long maximumTripletValue(int[] nums) {
long ans = 0;
int maxDiff = 0;
int preMax = 0;
for (int x : nums) {
ans = Math.max(ans, (long) maxDiff * x);
maxDiff = Math.max(maxDiff, preMax – x);
preMax = Math.max(preMax, x);
}
return ans;
}
}

套路

我们不难发现前面的三道题的思路总体上都是一致的，都是枚举中间位置 结合 前后缀分解。

我总结为这三个步骤：

• 选定枚举中间的那个变量j
• 使用哈希表或者数组预存右侧的信息
• 从左往右遍历，边遍历边更新左侧信息，同时更新答案

本质上，这类问题都是在固定一个“支点”，将三元关系 解耦为左右两侧的独立统计问题，再通过乘法原理合并

刚才我们解决的都是数组中的线性三元组问题，通过枚举中间的j来解耦左右，那么，如果问题变成二维平面上的点集呢？

我们再看一个题：

题目链接：https://leetcode.cn/problems/number-of-boomerangs/

思路

什么是欧几里得距离（Euclidean Distance）？

欧几里得距离就是我们在初中几何里学到的两点之间的直线距离。

假设平面上有两个点 $A(x_1,y_1)$ 和 $B(x_2,y_2)$，它们之间的距离公式为：$$d=\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2}$$

为了避免处理根号带来的浮点数精度问题，我们通常直接比较距离的平方：$$d^2=(x_1-x_2{)}^2+(y_1-y_2{)}^2$$

代码

class Solution {
public int numberOfBoomerangs(int[][] points) {
int ans = 0;
Map<Integer,Integer> cnt = new HashMap<>();
for(int [] p1 : points) {
cnt.clear();
for(int [] p2 : points) {
//计算两点之间的距离dis
int dis = (p1[0] – p2[0])* (p1[0] – p2[0]) + (p1[1] – p2[1])* (p1[1] – p2[1]);
//取出cnt中距离为dis的个数
int c = cnt.getOrDefault(dis, 0);
//统计答案，这个就是乘法原理
//*2是因为：回旋镖三元组(i,j,k)中，j和k可以互换位置，每一个组合都能形成两种顺序
ans += c * 2;//c * 1 * 2;
cnt.put(dis, c+1);

}
}
return ans;
}
}

总结

通过这几道题的练习，我们可以发现，虽然题目背景从一维数组（三元组）跨越到了二维平面（回旋镖），但其底层逻辑是高度统一的。

所以在写这种题的时候要记住：公式是死的，但思维是活的，不要死板地寻找 $i,j,k$： 在数组里，它们是索引；在坐标系里，它们是点；在字符串里，它们可能是字符。

望这篇总结能帮你建立起对三元组问题的直觉！如果你觉得有帮助，欢迎点赞收藏！