难度: 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 <= 1000 <= arr[i] <= 10000 <= a, b, c <= 1000运行时间: 139 ms
内存: 16.1 MB
class Solution:
def countGoodTriplets(self, arr: List[int], a: int, b: int, c: int) -> int:
count = 0
for idx,i in enumerate(arr[:-2]):
id = 0
for j in arr[idx+1:-1]:
id += 1
if abs(i-j)<=a:
for k in arr[idx+id+1:]:
if abs(j-k)<=b and abs(i-k)<= c:
count += 1
return count
题解采用了三层嵌套循环来枚举所有可能的三元组 (i, j, k)，其中 i < j < k。外层循环遍历数组arr以选择第一个元素i，中层循环从i之后开始遍历以选择第二个元素j，内层循环从j之后开始遍历以选择第三个元素k。对于每一个可能的三元组，检查是否满足题目中给定的三个条件：|arr[i] - arr[j]| <= a, |arr[j] - arr[k]| <= b, 和 |arr[i] - arr[k]| <= c。若满足这些条件，计数器count增加1。
时间复杂度: O(n^3)
空间复杂度: O(1)
class Solution:
def countGoodTriplets(self, arr: List[int], a: int, b: int, c: int) -> int:
count = 0 # 初始化计数器
for idx, i in enumerate(arr[:-2]): # 遍历到倒数第三个元素，作为三元组的第一个元素
id = 0 # 用于控制第三个元素的索引
for j in arr[idx+1:-1]: # 遍历第一个元素之后的元素，作为三元组的第二个元素
id += 1
if abs(i-j) <= a: # 检查第一和第二个元素的条件
for k in arr[idx+id+1:]: # 遍历第二个元素之后的元素，作为三元组的第三个元素
if abs(j-k) <= b and abs(i-k) <= c: # 检查第二和第三个元素以及第一和第三个元素的条件
count += 1 # 若满足条件，计数器增加
return count # 返回计数器的值
通过排序数组，可以在某些情况下减少内层循环的迭代次数。例如，如果数组已排序，我们可以使用二分搜索或双指针技术来快速找到满足条件的元素范围，从而减少内层循环的迭代次数。然而，对于本题中的条件 |arr[i] - arr[j]| <= a 和 |arr[j] - arr[k]| <= b 以及 |arr[i] - arr[k]| <= c，排序可能会使得快速确定满足这些条件的k较为复杂，因为需要同时保证三个条件。因此，虽然排序有助于某些情况，但实际操作中可能需要结合其他策略，如双指针等，来有效减少迭代次数。
在当前算法中，一旦发现 |arr[i] - arr[j]| > a，即可提前跳出内层循环，因为后续的所有j对于当前的i都不可能再满足 |arr[i] - arr[j]| <= a 的条件。这种提前终止循环的策略可以有效减少不必要的计算，提高算法的效率。
对数组进行排序可以帮助某些算法更高效地执行，但在这个特定的问题中，排序可能不会提供明显的好处，因为我们需要考虑的是三个不同元素间的相对差异。排序可能改变元素间原有的索引关系，这对于保持i < j < k的顺序是有影响的。如果考虑排序，可能需要更复杂的逻辑来保证条件还能被正确地检验。因此，排序在这种情况下可能不是最优的预处理步骤。
提供一个方法来输出所有满足条件的好三元组的具体值可以帮助更好地理解算法如何工作以及它的结果。这可以通过修改算法来实现，比如使用一个列表来存储所有满足条件的三元组，然后返回这个列表。这不仅帮助验证算法的正确性，也为调试和学习提供了更多的信息。然而，这会增加空间复杂度，因为需要额外的空间来存储所有符合条件的三元组。