Easy

题目描述

给你一个整数数组 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

解题思路

这道题要求我们找到满足三个条件的三元组数量。由于数组长度最大只有100，我们可以使用暴力枚举的方法。

解题思路：

观察到数据规模较小（n ≤ 100），可以直接使用三重循环暴力枚举所有可能的三元组。对于每个三元组 (i, j, k)，其中 0 <= i < j < k < n，我们需要检查：

  1. |arr[i] - arr[j]| <= a
  2. |arr[j] - arr[k]| <= b
  3. |arr[i] - arr[k]| <= c

如果三个条件都满足，计数器加1。

算法步骤：

  1. 初始化计数器 count = 0
  2. 使用三重循环遍历所有满足 i < j < k 的索引组合
  3. 对每个三元组检查三个绝对值条件
  4. 如果都满足，count++
  5. 返回最终计数

由于约束条件保证了暴力解法的可行性，这是最直观且高效的解决方案。时间复杂度为 O(n³)，在给定数据规模下完全可以接受。

代码实现

class Solution {
public:
    int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
        int count = 0;
        int n = arr.size();
        
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (abs(arr[i] - arr[j]) <= a && 
                        abs(arr[j] - arr[k]) <= b && 
                        abs(arr[i] - arr[k]) <= c) {
                        count++;
                    }
                }
            }
        }
        
        return count;
    }
};

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

public class Solution {
    public int CountGoodTriplets(int[] arr, int a, int b, int c) {
        int count = 0;
        int n = arr.Length;
        
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int 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) {
                        count++;
                    }
                }
            }
        }
        
        return count;
    }
}

var countGoodTriplets = function(arr, a, b, c) {
    let count = 0;
    const n = arr.length;
    
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; 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) {
                    count++;
                }
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n³)三重嵌套循环遍历所有三元组
空间复杂度O(1)只使用常数级别的额外空间

相关题目