1534. 统计好三元组
问题分析
遍历数组，满足好三元组定义，count+=1
思路
枚举i，j，k
代码
class Solution:def countGoodTriplets(self, arr: List[int], a: int, b: int, c: int) -> int:n = len(arr)count = 0for 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 += 1return count复杂度分析
时间复杂度，3个for循环，O(N^3)
空间复杂度：O（1）
学习
复杂度优化：
class Solution:def countGoodTriplets(self, arr: List[int], a: int, b: int, c: int) -> int:ans = 0mx = max(arr)s = [0] * (mx + 2) # cnt 数组的前缀和for j, y in enumerate(arr):for z in arr[j + 1:]:if abs(y - z) > b:continuel = max(y - a, z - c, 0)r = min(y + a, z + c, mx)ans += max(s[r + 1] - s[l], 0) # 如果 l > r + 1，s[r + 1] - s[l] 可能是负数for v in range(y + 1, mx + 2):s[v] += 1 # 把 y 加到 cnt 数组中，更新所有受到影响的前缀和return ans
复杂度分析
时间复杂度：O(n(n+U))，其中 n 是 arr 的长度，U=max(arr)。
空间复杂度：O(U)。Python 忽略切片空间。
学习来源：
作者：灵茶山艾府
链接：https://leetcode.cn/problems/count-good-triplets/solutions/3622921/liang-chong-fang-fa-bao-li-mei-ju-qian-z-apcv/
来源：力扣（LeetCode）
