当前位置：首页 > news >正文

力扣每日打卡 1534. 统计好三元组 (简单)

news 来源：原创 2025/8/27 5:20:34

力扣 1534. 统计好三元组简单

前言
一、题目内容
二、解题方法
- 1. 暴力解法
- 2.官方题解
- - 2.1 方法一：枚举
  - 2.2 方法二：枚举优化

前言

这是刷算法题的第十二天，用到的语言是JS
题目：力扣 1534. 统计好三元组 (简单)

一、题目内容

给你一个整数数组 arr ，以及 a、b 、c 三个整数。请你统计其中好三元组的数量。

如果三元组 $(a rr [i], a rr [j], a rr [k])$ 满足下列全部条件，则认为它是一个好三元组。

$0 <= i < j < k < a rr . l e n g t h$
$∣ a rr [i] - a rr [j] ∣ <= a$
$∣ a rr [j] - a rr [k] ∣ <= b$
$∣ a rr [i] - a rr [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 <= a rr . l e n g t h <= 100$
$0 <= a rr [i] <= 1000$
$0 <= a, b, c <= 1000$

二、解题方法

1. 暴力解法

三重for循环

代码如下（实例）：

/*** @param {number[]} arr* @param {number} a* @param {number} b* @param {number} c* @return {number}*/
var countGoodTriplets = function (arr, a, b, c) {// 暴力算法let count = 0for (let i = 0; i < arr.length; i++) for (let j = i + 1; j < arr.length; j++) for (let k = j + 1; k < arr.length; k++) if (Math.abs(arr[i] - arr[j]) <= a && Math.abs(arr[j] - arr[k]) <= b && Math.abs(arr[i] - arr[k]) <= c) count++return count
}

2.官方题解

2.1 方法一：枚举

思路与算法

用 $O(n^3)$ 的循环依次枚举所有的 $(i, j, k)$ ，这里 $0 \leq i < j < k < a rr . l e n g t h$ ，对于每组 $(i, j, k)$ ，判断 $a rr [i] 、 a rr [j] 、 a rr [k]$ 是否满足条件。

最终统计出所有满足条件的三元组的数量。

代码如下（示例）：

var countGoodTriplets = function(arr, a, b, c) {const n = arr.length;let cnt = 0;for (let i = 0; i < n; ++i) {for (let j = i + 1; j < n; ++j) {for (let k = j + 1; k < n; ++k) {if (Math.abs(arr[i] - arr[j]) <= a && Math.abs(arr[j] - arr[k]) <= b && Math.abs(arr[i] - arr[k]) <= c) {++cnt;}}}}return cnt;
};作者：力扣官方题解
链接：https://leetcode.cn/problems/count-good-triplets/solutions/371340/tong-ji-hao-san-yuan-zu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析：

时间复杂度：

O(n^3)

，其中

n

是数组

a rr

的长度。

空间复杂度：

O (1)

链接：力扣本题官方题解
来源：力扣（LeetCode）

2.2 方法二：枚举优化

思路与算法
我们考虑 $O(n^2)$ 枚举满足 $∣ a rr [j] - a rr [k] ∣\leq b$ 的二元组 $(j, k)$ ，统计这个二元组下有多少 $i$ 满足条件。由题目已知 $i$ 的限制条件为 $∣ a rr [i] - a rr [j] ∣\leq a$ && $∣ a rr [i] - a rr [k] ∣\leq c$ ，我们可以拆开绝对值，得到符合条件的值一定是 $[a rr [j] - a, a rr [j] + a]$ 和 $[a rr [k] - c, a rr [k] + c]$ 两个区间的交集，我们记为 $[l, r]$ 。因此，在枚举 $(j, k)$ 这个二元组的时候，我们只需要快速统计出满足 $i < j$ 且 $a rr [i]$ 的值域范围在 $[l, r]$ 的 $i$ 的个数即可。

很容易想到维护一个 $a rr [i]$ 频次数组的前缀和 $s u m$ ，对于一个二元组 $(j, k)$ ，我们可以 $O (1)$ 得到答案为 $s u m [r] - s u m [l - 1]$ 。考虑怎么维护保证当前频次数组存的数的下标符合 $i < j$ 的限制，我们只要从小到大枚举 $j$ ，每次 $j$ 移动指针加一的时候，将 $a rr [j]$ 的值更新到 $s u m$ 数组中即可，这样能保证枚举到 $j$ 的时候 $s u m$ 数组里存的值的下标满足限制。

「将 $a rr [j]$ 的值更新到 $s u m$ 数组中」这个操作在本方法中是暴力更新，因为数组的值域上限很小，有能力的读者可以考虑怎么在进一步优化这一部分的复杂度，可以从离散化或者树状数组的角度考虑，这里不再赘述。

代码如下（示例）：

var countGoodTriplets = function(arr, a, b, c) {const n = arr.length, sum = new Array(1001).fill(0);let ans = 0;for (let j = 0; j < n; ++j) {for (let k = j + 1; k < n; ++k) {if (Math.abs(arr[j] - arr[k]) <= b) {const lj = arr[j] - a, rj = arr[j] + a;const lk = arr[k] - c, rk = arr[k] + c;const l = Math.max(0, Math.max(lj, lk)), r = Math.min(1000, Math.min(rj, rk));if (l <= r) {if (l === 0) {ans += sum[r];}else {ans += sum[r] - sum[l - 1];}}}}for (let k = arr[j]; k <= 1000; ++k) {sum[k] += 1;}}return ans;
};作者：力扣官方题解
链接：https://leetcode.cn/problems/count-good-triplets/solutions/371340/tong-ji-hao-san-yuan-zu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析：

时间复杂度：

O(n^2+nS)

，其中

n

是数组

a rr

的长度，

S

为数组的值域上限，这里为

1000

。

空间复杂度：

O (S)

。我们需要

O (S)

的空间维护

a rr [i]

频次数组的前缀和。