1534. 统计好三元组 - 力扣（LeetCode）
题目
给你一个整数数组 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
思路
- 还是和上题一样的思路，但是变成3重循环再判断。
代码实现
class Solution {
public:int countGoodTriplets(vector<int>& arr, int a, int b, int c) {int cnt = 0, n = arr.size()-2;for(int i = 0; i < n; ++i) {for(int j = i+1; j < n+1; ++j) {if(abs(arr[i]-arr[j]) <= a) {for(int k = j+1; k < n+2; ++k) {if(abs(arr[j]-arr[k])<=b && abs(arr[i]-arr[k])<=c) ++cnt;}}}}return cnt;}
};复杂度分析
- 时间复杂度：O(n^3)。
- 空间复杂度：O(1)。
题解
- 官方题解还有一个将时间复杂度优化到O(n^2)的思路，那不得不看了。
- 因为确定了其中两个点的值后，第三个点的可选范围就可以由那两个定点来表出。往后的数据都是还没访问的统计不到，所以可以直接选择控制后面的两个点，然后去框定第一个点的范围。
- 假设已经确定了arr[j]和arr[k]，那么i的取值范围就是[arr[j]-a, arr[j]+a]和[arr[k]-c, arr[k]+c]的交集（当然，arr[i]的取值范围只在[0, 1000]），所以我们只用统计由多少个在这个范围内的arr[i]即可。
- 那么这个arr[i]怎么统计呢？因为满足要求的i第一是要小于j和k，所以每次j判断完之后直接[arr[j], 1000]范围内的数量加1，这样就统计了之前的arr[i]的个数了。
- 进一步地，因为arr[i]的范围是不会超过这个数组中的范围，所以我们可以将更新i个数和保存i个数数组的复杂度简化为数组的最大值，那么我们就可以做比较大的剪枝了。
- 复现：
-
class Solution { public:int countGoodTriplets(vector<int>& arr, int a, int b, int c) {int cnt = 0, mx = ranges::max(arr), n = arr.size();vector<int> arris(mx+2, 0);for(int j = 0; j < n; ++j) {for(int k = j+1; k < n; ++k) {if(abs(arr[j]-arr[k]) <= b) {int lj = arr[j] - a, rj = arr[j] + a, lk = arr[k] - c, rk = arr[k] + c;int l = max(0, max(lj, lk)), r = min(mx, min(rj, rk));if(l <= r) {if(l == 0) cnt += arris[r];else cnt += arris[r] - arris[l-1];}}}for(int k = arr[j]; k <= mx; ++k) ++arris[k]; // 题解说这部分可以优化，可以想想}return cnt;} }; - 时间复杂度：O(n^2+nS)，S为mx的值，最大为1000——那么时间复杂度可能就会跟S的大小相关了，如果S远大于n，那么时间复杂度将会非常差。
- 空间复杂度：O(S)。
- 更进一步，还有大佬提出了一个与S无关的方法，就是先建立一个对应的下标数组，但是这个下标是按arr[i]的值排序的。
- 那么就直接遍历这个数组，在其中再创建left数组和right数组分别存储满足i<j且|arr[i]-arr[j]|<=a的arr[i]和k>j且|arr[j]-arr[k]|<=b的arr[k]。
- 最后就会得到两个有序的数组，再遍历left数组的过程找right中满足|arr[i]-arr[k]|<=c的上下界，那么我们就可以知道符合要求i，k对个数了。
- 上面总共两层循环，每个内层循环的最坏时间复杂度是O(n)，所以总的时间复杂度是O(n^2)的，而新建的数组也不会超过O(n)，空间复杂度则是O(n)的，那么时空间复杂度就和S无关了。
- 复现：
-
class Solution { public:int countGoodTriplets(vector<int>& arr, int a, int b, int c) {int cnt = 0, n = arr.size();vector<int> idxs;for(int i = 0; i < n; ++i) {idxs.push_back(i);}sort(idxs.begin(), idxs.end(), [&](int i, int j) {if(arr[i] == arr[j]) return i < j;else return arr[i] < arr[j];});for(int j = 0; j < n; ++j) {int idxj = idxs[j];int value = arr[idxj];vector<int> left, right;for(int i = 0; i < n; ++i) {int idxi = idxs[i];if(idxi < idxj && abs(arr[idxi]-value)<=a) left.push_back(arr[idxi]);else if(arr[idxi]-arr[idxj] > a) break;}for(int k = 0; k < n; ++k) {int idxk = idxs[k];if(idxk > idxj && abs(value-arr[idxk])<=b) right.push_back(arr[idxk]);else if(arr[idxk]-arr[idxj] > b) break;}int l = 0, r = 0;// 这里的l和r都是直接继承的，所以l和r的++次数不会超过2n次，所以即使是双重循环复杂度仍然是O(n)的。for(int i = 0; i < left.size(); ++i) {while(r < right.size() && right[r] <= left[i]+c) ++r;while(l < right.size() && right[l] < left[i]-c) ++l;cnt += r-l;}}return cnt;} }; - 但是因为本题的S比较小，所以这个解法是比官解的时间开销大的。
