LeetCode 1534: Count Good Triplets (Triple Enumeration with Early Pruning Bounds)
LeetCode 1534ArrayEnumerationPruningToday we solve LeetCode 1534 - Count Good Triplets.
Source: https://leetcode.com/problems/count-good-triplets/
English
Problem Summary
Given an integer array arr and integers a, b, c, count triplets (i, j, k) such that 0 <= i < j < k < arr.length and all constraints hold:
|arr[i] - arr[j]| <= a, |arr[j] - arr[k]| <= b, and |arr[i] - arr[k]| <= c.
Key Insight
The constraints are local and n is at most 100, so direct triple enumeration is acceptable. We can still prune early: if (i,j) already fails the a condition, skip all k for that pair.
Brute Force and Limitations
Full three-loop enumeration checks all index triples and validates three inequalities, which is O(n^3). For this problem size it is fast enough and simpler than over-engineering.
Optimal Algorithm Steps
1) Loop i from left to right.
2) Loop j > i; if |arr[i]-arr[j]| > a, continue.
3) Loop k > j and check remaining two conditions.
4) Count each valid triple.
Complexity Analysis
Time: O(n^3).
Space: O(1).
Common Pitfalls
- Forgetting strict index ordering i < j < k.
- Using only two of the three inequality conditions.
- Accidentally counting value combinations instead of index triplets.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int countGoodTriplets(int[] arr, int a, int b, int c) {
int n = arr.length;
int ans = 0;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
if (Math.abs(arr[i] - arr[j]) > a) {
continue;
}
for (int k = j + 1; k < n; k++) {
if (Math.abs(arr[j] - arr[k]) <= b &&
Math.abs(arr[i] - arr[k]) <= c) {
ans++;
}
}
}
}
return ans;
}
}func countGoodTriplets(arr []int, a int, b int, c int) int {
n := len(arr)
ans := 0
abs := func(x int) int {
if x < 0 {
return -x
}
return x
}
for i := 0; i < n-2; i++ {
for j := i + 1; j < n-1; j++ {
if abs(arr[i]-arr[j]) > a {
continue
}
for k := j + 1; k < n; k++ {
if abs(arr[j]-arr[k]) <= b && abs(arr[i]-arr[k]) <= c {
ans++
}
}
}
}
return ans
}class Solution {
public:
int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
int n = (int)arr.size();
int ans = 0;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
if (abs(arr[i] - arr[j]) > a) continue;
for (int k = j + 1; k < n; k++) {
if (abs(arr[j] - arr[k]) <= b && abs(arr[i] - arr[k]) <= c) {
ans++;
}
}
}
}
return ans;
}
};class Solution:
def countGoodTriplets(self, arr: list[int], a: int, b: int, c: int) -> int:
n = len(arr)
ans = 0
for i in range(n - 2):
for j in range(i + 1, n - 1):
if abs(arr[i] - arr[j]) > a:
continue
for k in range(j + 1, n):
if abs(arr[j] - arr[k]) <= b and abs(arr[i] - arr[k]) <= c:
ans += 1
return ansvar countGoodTriplets = function(arr, a, b, c) {
const n = arr.length;
let ans = 0;
for (let i = 0; i < n - 2; i++) {
for (let j = i + 1; j < n - 1; j++) {
if (Math.abs(arr[i] - arr[j]) > a) continue;
for (let k = j + 1; k < n; k++) {
if (Math.abs(arr[j] - arr[k]) <= b && Math.abs(arr[i] - arr[k]) <= c) {
ans++;
}
}
}
}
return ans;
};中文
题目概述
给定整数数组 arr 以及整数 a、b、c，统计满足 0 <= i < j < k < arr.length 的三元组数量，并且三条约束都成立：
|arr[i] - arr[j]| <= a、|arr[j] - arr[k]| <= b、|arr[i] - arr[k]| <= c。
核心思路
本题数据范围 n <= 100，三重枚举是可接受的。可以做一个小剪枝：若 (i,j) 已经不满足第一条约束，就不用继续枚举该对下的所有 k。
暴力解法与不足
直接三层循环检查所有三元组，时间复杂度是 O(n^3)。虽然不是最“优雅”的大规模方案，但在本题约束下最稳、最清晰。
最优算法步骤
1）枚举左端点 i。
2）枚举中间点 j；若 |arr[i]-arr[j]| > a 直接跳过。
3）枚举右端点 k，检查另外两条约束。
4）三条都满足则计数加一。
复杂度分析
时间复杂度：O(n^3)。
空间复杂度：O(1)。
常见陷阱
- 下标顺序写错，没保证 i < j < k。
- 漏掉第三个不等式条件。
- 把“值组合”当成“下标三元组”去重，导致计数错误。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int countGoodTriplets(int[] arr, int a, int b, int c) {
int n = arr.length;
int ans = 0;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
if (Math.abs(arr[i] - arr[j]) > a) {
continue;
}
for (int k = j + 1; k < n; k++) {
if (Math.abs(arr[j] - arr[k]) <= b &&
Math.abs(arr[i] - arr[k]) <= c) {
ans++;
}
}
}
}
return ans;
}
}func countGoodTriplets(arr []int, a int, b int, c int) int {
n := len(arr)
ans := 0
abs := func(x int) int {
if x < 0 {
return -x
}
return x
}
for i := 0; i < n-2; i++ {
for j := i + 1; j < n-1; j++ {
if abs(arr[i]-arr[j]) > a {
continue
}
for k := j + 1; k < n; k++ {
if abs(arr[j]-arr[k]) <= b && abs(arr[i]-arr[k]) <= c {
ans++
}
}
}
}
return ans
}class Solution {
public:
int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
int n = (int)arr.size();
int ans = 0;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
if (abs(arr[i] - arr[j]) > a) continue;
for (int k = j + 1; k < n; k++) {
if (abs(arr[j] - arr[k]) <= b && abs(arr[i] - arr[k]) <= c) {
ans++;
}
}
}
}
return ans;
}
};class Solution:
def countGoodTriplets(self, arr: list[int], a: int, b: int, c: int) -> int:
n = len(arr)
ans = 0
for i in range(n - 2):
for j in range(i + 1, n - 1):
if abs(arr[i] - arr[j]) > a:
continue
for k in range(j + 1, n):
if abs(arr[j] - arr[k]) <= b and abs(arr[i] - arr[k]) <= c:
ans += 1
return ansvar countGoodTriplets = function(arr, a, b, c) {
const n = arr.length;
let ans = 0;
for (let i = 0; i < n - 2; i++) {
for (let j = i + 1; j < n - 1; j++) {
if (Math.abs(arr[i] - arr[j]) > a) continue;
for (let k = j + 1; k < n; k++) {
if (Math.abs(arr[j] - arr[k]) <= b && Math.abs(arr[i] - arr[k]) <= c) {
ans++;
}
}
}
}
return ans;
};
Comments