[LeetCode] 每日一题 1534. 统计好三元组（暴力法 & 前缀和优化）
题目描述
给你一个整数数组 arr ，以及 a、b 、c 三个整数。请你统计其中好三元组的数量。
如果三元组 (arr[i], arr[j], arr[k]) 满足下列全部条件，则认为它是一个 好三元组 。
0 <= i < j < k < arr.length|arr[i] - arr[j]| <= a|arr[j] - arr[k]| <= b|arr[i] - arr[k]| <= c
其中 |x| 表示 x 的绝对值。
返回 好三元组的数量 。
题目链接
示例输入
示例 1
输入：arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
输出：4
解释：一共有 4 个好三元组：[(3,0,1), (3,0,1), (3,1,1), (0,1,1)] 。示例 2
输入：arr = [1,1,2,2,3], a = 0, b = 0, c = 1
输出：0
解释：不存在满足所有条件的三元组。提示
3 <= arr.length <= 1000 <= arr[i] <= 10000 <= a, b, c <= 1000
解题思路
这题属于典型的简单题，一读题其实就知道暴力枚举三元组 (i, j, k) 是最直接的解法，判断三个条件是否都满足即可。
暴力解法非常直观：
三重 for 循环分别遍历 i < j < k 的组合；
判断
|arr[i] - arr[j]| <= a，|arr[j] - arr[k]| <= b，|arr[i] - arr[k]| <= c；如果全部满足就统计一次。
这种写法时间复杂度是 O(n³)，在数据范围较小时可直接使用，代码如下 👇：
class Solution {
public int countGoodTriplets(int[] arr, int a, int b, int c) {
int n = arr.length;
int count = 0;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
if (Math.abs(arr[i] - arr[j]) <= a &&
Math.abs(arr[j] - arr[k]) <= b &&
Math.abs(arr[i] - arr[k]) <= c) {
count++;
}
}
}
}
return count;
}
}不过这题更有意思的地方在于：可以用前缀和进行优化！
思路如下：
固定
j和k后，三元组是否成立只与arr[i]的取值有关；将三个条件转化为
arr[i]需要落在某个范围之内；这三个范围可以求交集，得到有效的
arr[i]范围[l, r]；那么只要知道这个区间内的
arr[i]出现了多少次，就可以加到答案里了。
我们通过构造一个频次数组 cnt[] 和它的前缀和 sum[] 来实现这个统计：
class Solution {
public int countGoodTriplets(int[] arr, int a, int b, int c) {
int max = 0;
for (int x : arr) {
max = Math.max(max, x);
}
int[] sum = new int[max + 2];
int ans = 0;
for (int j = 0; j < arr.length; j++) {
int y = arr[j];
for (int k = j + 1; k < arr.length; k++) {
int z = arr[k];
if (Math.abs(y - z) > b) {
continue;
}
int l = Math.max(Math.max(y - a, z - c), 0);
int r = Math.min(Math.min(y + a, z + c), max);
ans += Math.max(sum[r + 1] - sum[l], 0);
}
for (int v = y + 1; v < sum.length; v++) {
sum[v]++;
}
}
return ans;
}
}我们用 sum[v] 表示 [0, v - 1] 中所有数字在 arr 中出现的次数。这样就能用 O(1) 的时间查询任意区间 [l, r] 中元素的出现次数，极大减少时间开销 🎯
复杂度分析
暴力解法：
时间复杂度： O(n³)
空间复杂度： O(1)
前缀和优化解法：
时间复杂度： O(n² + n * maxVal)（其中
maxVal是数组中元素的最大值）空间复杂度： O(maxVal) 用于记录频次和前缀和数组
✨ 注意：前缀和法在数组元素范围较小时效果极佳，非常适合用于存在“值域不大”但“数据量大”的题目！
总结
这这道题虽然是简单题，但非常适合练习从暴力到优化的思维迁移。特别是前缀和的使用让我联想到刷过的很多计数类问题——用值域 + 计数数组能有效规避掉三重循环，效率提升非常显著。
前缀和技巧可以说是做数组题时的万金油工具之一，遇到频次统计和区间查询场景都值得优先考虑 💡
希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。