题目描述

现在给定一个数组arr，和a,b两个数字，你要做的就是找到（i，j，k）。且满足
1. 0 <= i < j < k < arr.size()
2. |arr[i] - arr[j]| <= a
3. |arr[j] - arr[k]| <= b
统计满足条件的个数并返回(最后结果可能很大，请取1000000007的余数)。

样例1

输入
[7,1,8,9,0],3,3
返回值
1

说明

只有（7，8，9）符合要求

备注:

0 < m < 100
0 < n < 2000

题解

对于本题，我们最先想到的一定是暴力的遍历方法，那么时间复杂度则会达到 O(n3)，结合本题数据，这是不可行的，所以我们必须考虑优化。那么就可以想到题目要求中与 i , k 均有关的 j ,只需要分别计算左侧满足条件1和右边条件2的数量x , y，则 ans += x*y,具体代码如下：

int countTriplets(vector<int>& arr, int a, int b) {
        const int MOD = 1000000007;
        int n = arr.size();
        long long  ans = 0;
        for (int j = 1; j < n - 1; j++) {
            long  long x = 0;
            long  long y = 0;
            for (int i = 0; i < j; i++) {
                if(abs(arr[i] - arr[j]) <= a)
                    x++;
            }
            for (int k = j + 1; k < n; k++) {
                if (abs(arr[k] - arr[j]) <= b)
                    y++;
            }
            ans += x * y;
            ans %= MOD;
        }
        return (int)(ans%MOD);
    }