class Solution {
public:
int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
vector<int> idx(arr.size());
ranges::iota(idx, 0);
ranges::sort(idx, {}, [lbk]&[rbk](int i) { return arr[lbk]i[rbk]; });
//索引排序
int ans = 0;
for (int j : idx) {
int y = arr[lbk]j[rbk];
vector<int> left, right;
for (int i : idx) {
if (i < j && abs(arr[lbk]i[rbk] - y) <= a) {
left.push_back(arr[lbk]i[rbk]);
}
}
for (int k : idx) {
if (k > j && abs(arr[lbk]k[rbk] - y) <= b) {
right.push_back(arr[lbk]k[rbk]);
}
}
//双指针
for(int m = 0, n1 = 0, n2 = 0;m < left.size(); m++){
while(n1 < right.size() && right[lbk]n1[rbk] < left[lbk]m[rbk] - c){
n1++;
}
while(n2 < right.size() && right[lbk]n2[rbk] <= left[lbk]m[rbk] + c){
n2++;
}
ans += n2 - n1;
}
}
return ans;
}
};
时间复杂度O(n^2)
空间复杂度O(n)
此解法约难度分2000