LeetCode

Appearance

1534. Count Good Triplets ​

题目 ​

Given an array of integers arr, and three integers a, b and c. You need to find the number of good triplets.

A triplet (arr[i], arr[j], arr[k]) is good if the following conditions are true:

  • 0 <= i < j < k < arr.length
  • |arr[i] - arr[j]| <= a
  • |arr[j] - arr[k]| <= b
  • |arr[i] - arr[k]| <= c

Where |x| denotes the absolute value of x.

Return the number of good triplets.

 

Example 1:

Input: arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
Output: 4
Explanation: There are 4 good triplets: [(3,0,1), (3,0,1), (3,1,1), (0,1,1)].

Example 2:

Input: arr = [1,1,2,2,3], a = 0, b = 0, c = 1
Output: 0
Explanation: No triplet satisfies all conditions.

 

Constraints:

  • 3 <= arr.length <= 100
  • 0 <= arr[i] <= 1000
  • 0 <= a, b, c <= 1000
Related Topics
  • 数组
  • 枚举

  • 👍 153
  • 👎 0

    • 思路 ​

    解法 ​

    py
    from typing import List

# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def countGoodTriplets(self, arr: List[int], a: int, b: int, c: int) -> int:

        mx = max(arr)
        size = len(arr)

        s = [0] * (mx + 2)

        ans = 0

        for j, _ in enumerate(arr):
            for k in range(j + 1, size):
                if (abs(arr[j] - arr[k]) > b):
                    continue
                l = max(arr[j] - a, arr[k] - c, 0)
                r = min(arr[j] + a, arr[k] + c, mx)
                # arr[i] 的约束条件为 l <= arr[i] <= r && i < j
                if l > r:
                    continue
                ans += s[r + 1] - s[l]

            # 维系一个前缀和数组，跟传统的前缀和数组不同的是，s[k]表示 range 区间
            # 若arr[j] = 10, 则arr的值在 10 - 1001 区间中，大于10的值均加一
            for k in range(arr[j] + 1, (mx + 2)):
                s[k] += 1

        return ans

# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    • 时间复杂度O(n2)
    • 空间复杂度O(N), N <= max(nums) <= 1002