题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个数组，要求统计其中所有满足要求三元组的数量。该要求是，两两之差，满足题目的三个数字。

思路分享

代码解答（强烈建议自行解答后再看）

  • 陆爻齐小改良的暴力解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
        int size = arr.size();
        int result = 0;
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                if (abs(arr[i] - arr[j]) > a) continue;
                for (int k = j + 1; k < size; k++) {
                    if (abs(arr[j] - arr[k]) <= b && abs(arr[i]-arr[k]) <= c) {
                        //cout << arr[i] << " " << arr[j] << " " << arr[k] << endl;
                        result++;
                    }
                }
            }
        }
        return result;
    }
};
  • 前缀和解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
        int n = arr.size(), mx = ranges::max(arr), ans = 0;
        vector<int> s(mx+2);
        for (int j = 0; j < arr.size(); j++) {
            int y = arr[j];
            for (int k = j + 1; k < arr.size(); k++) {
                int z = arr[k];
                if (abs(y-z) > b) continue;
                int l = max({y-a, z-c, 0});
                int r = min({y+a, z+c, mx});
                ans += max(s[r+1]-s[l], 0);
            }
            for (int v = y+1; v < mx+2; v++) {
                s[v]++;
            }
        }
        return ans;
    }
};