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 <= 100
0 <= arr[i] <= 1000
0 <= a, b, c <= 1000

解题思路

统计好三元组的问题可以化简为统计满足 ∣arr[j]−arr[k]∣≤b 条件的二元组 (j,k) 中有多少 i 满足条件。由题意可知 |arr[i] - arr[j]| <= a 且 |arr[i] - arr[k]| <= c 因此 arr[i] 一定是 [arr[j] - a,arr[j] + a] 和 [arr[k]−c,arr[k]+c] 两个区间的交集，此时我们只需要统计出满足 i<j 且 arr[i] 处在上述交集区间的 i 的个数即可。这时我们可以维护一个 arr[i] 频次数组的前缀和 sum。这样就只需要考虑怎么维护保证当前频次数组存的数的下标符合 i<j 的限制，我们只要从小到大枚举 j，每次 j 移动指针加一的时候，将 arr[j] 的值更新到 sum 数组中即可，这样能保证枚举到 j 的时候 sum 数组里存的值的下标满足限制。

复杂度分析

时间复杂度：O(n² + m * n)，其中 n 为数组 arr 的长度，m 为 sum 数组的长度 1000。
空间复杂度：O(m)。

代码实现

class Solution {
    public int countGoodTriplets(int[] arr, int a, int b, int c) {
        int res = 0, n = arr.length;
        int[] sum = new int[1001];
        for (int j = 0; j < n; j ++) {
            for (int k = j + 1 ; k < n; k ++) {
                if (Math.abs(arr[j] - arr[k]) <= b) {
                    int lj = arr[j] - a, rj = arr[j] + a;
                    int lk = arr[k] - c, rk = arr[k] + c;
                    int l = Math.max(0, Math.max(lj, lk)), r = Math.min(1000, Math.min(rj, rk));
                    if (l <= r) {
                        if (l == 0) {
                            res += sum[r];
                        }
                        else {
                            res += sum[r] - sum[l - 1];
                        }
                    }
                }
            }
            for (int k = arr[j]; k <= 1000; k ++) {
                sum[k] ++;
            }
        }
        return res;
    }
}