What is the best approach to solve Count Good Triplets?

Directly enumerate all triplets i < j < k and check the three absolute difference conditions. With small constraints, brute-force works efficiently.

Can I optimize beyond brute-force for large arrays?

For larger arrays, techniques like prefix sums or frequency counting may help, but for this problem's size, simple enumeration is sufficient.

Why do I need to check all three absolute differences?

Each condition filters invalid triplets. Missing any condition will overcount, violating the problem's Array plus Enumeration pattern.

How does index ordering affect the solution?

Indices must satisfy i < j < k; swapping indices or allowing equality can count invalid triplets, leading to wrong results.

Does GhostInterview provide automatic triplet validation?

Yes, it highlights which triplets pass or fail conditions and ensures all enumerated combinations are accurately counted.

#1534

Easy

auto_awesome数组·结合·enumeration

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

lightbulb

解题思路

方法一：枚举

我们可以枚举所有的 $i$ , $j$ 和 $k$ ，其中 $i \lt j \lt k$ ，判断是否同时满足 $|\textit{arr}[i] - \textit{arr}[j]| \le a$ ， $|\textit{arr}[j] - \textit{arr}[k]| \le b$ 和 $|\textit{arr}[i] - \textit{arr}[k]| \le c$ ，如果满足则将答案加一。

枚举结束后，即可得到答案。

时间复杂度 $O(n^3)$ ，其中 $n$ 为数组 $\textit{arr}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def countGoodTriplets(self, arr: List[int], a: int, b: int, c: int) -> int:
        ans, n = 0, len(arr)
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    ans += (
                        abs(arr[i] - arr[j]) <= a
                        and abs(arr[j] - arr[k]) <= b
                        and abs(arr[i] - arr[k]) <= c
                    )
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n^3) in naive enumeration, but early breaks can reduce checks to roughly O(n^2) for most inputs. Space complexity is O(1) aside from storing input, as no additional structures are required.
空间	O(S)

psychology

面试官常问的追问

外企场景

question_mark
Asks if brute-force enumeration is acceptable given small constraints.
question_mark
Checks understanding of absolute difference and triplet conditions.
question_mark
Watches for correct index ordering to prevent miscounting.

warning

常见陷阱

外企场景

error
Using <= instead of < for indices, causing duplicates or invalid triplets.
error
Neglecting one of the three absolute difference conditions.
error
Overcomplicating with unnecessary data structures when direct enumeration suffices.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count good quadruplets with four absolute difference conditions.
arrow_right_alt
Find maximum sum of good triplets instead of count.
arrow_right_alt
Restrict triplets to unique values in the array.

help

常见问题

外企场景

继续练习

#1566 重复至少 K 次且长度为 M 的模式 #1601 最多可达成的换楼请求数目 #1620 网络信号最好的坐标