Day 19：1534. Count Good Triplets

今日题目

题目连结：1534. Count Good Triplets
题目主题：Array, Enumeration

分享完Binary Tree等等相关主题後，接下来开始会进入几个常见的演算法主题，Enumeration、Backtracking、Greedy、Divide And Conquer、Dynamic Programming，今天会先从Enumeration开始。

简单说说 Enumeration

Enumeration 演算法是最暴力最简单的演算法，基本上就是把所有可能性都列出来，可以找出所有符合条件的解、也可以找出最佳解，但相对的要用大量的时间来把所有可能列出来。

找一个范例来说明，假设 nums = [1, 2, 3, 4, 5]，想要在这个 nums 中找出所有三个数加起来等於 9 的组合，实际上 Enumeration 想像起来如下图：

简单来说就是把所有组合都列出来，把每种组合都做加总，再来看哪一条线符合目标值，从上图可以看得到 [1, 3, 5] 及 [2, 3, 4] 这两条线都等於 9。

如果今天想要找三个数加总以後最大的组合，也可以从上面的 Enumeration 范例图看到，12是最大的数字，那麽就可以找到 [3, 4, 5] 这个组合。

题目解说

建议可以看看LeetCode原本的题目说明，这边是用我的方式说明题目，参考就好。

题目会给一个 arr 的数组及 a、b、c 三个值，目标是从 arr 找出三个数组合起来，三个数的组合会是 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

要注意条件是相减後的绝对值。
最终要回传的是三个数组合符合条件的总数。

约束：

• 3 <= arr.length <= 100
• 0 <= arr[i] <= 1000
• 0 <= a, b, c <= 1000

范例1

输入: arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
输出: 4
解说: 举其中一个例子
    i       j       k
arr[0], arr[1], arr[2] = (3,0,1)
   0 < 1 < 2           True
  |3 - 0| = 3 , 3 <= 7 True
  |0 - 1| = 1 , 1 <= 2 True
  |3 - 1| = 2 , 2 <= 3 True
四个条件都成立，就算是符合条件，因此最後找出下面四个组合。
[(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
解说: 没有任何三个数符合条件，所以最後回传 0。

建议到这边先停下来，尝试自己解解看，若没有想法可再继续走下去。

解题的想像

文字描述

1. 写一个递回方法，最後回传符合条件的总数，需要传入以下：

   • Stack：用来存放三个数的组合
   • count：最终要回传的符合条件总数
   • arr、a、b、c 四个必要要素
   • startIdx：每一次要开始的位置

2. 递回方法每次执行会检查的条件如下：

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

3. 每次执行递回方法都会再执行一个回圈，这个回圈会处理以下几件事：

   • 每一圈开始时 Stack 放入一个值
   • 每一圈结束时 Stack 取出一个值
   • 检查是否都符合 2. 的条件
   • 发现 Stack 凑不到三个数字时，结束回圈

图解过程

范例：[3,0,1,1,9]、a = 7 , b = 2 , c = 3

上图可以看到红色数字指的是 i, j, k，绿色的部份是检查是否符合条件，其中绿色粗体是有符合条件的值，最後可看红色虚线方框，是完全符合条件的组合，总共有四个。实际上在程序的运作过程，会从左到右一个一个组合去确认是否完全符合条件。

若因为没想法而走到这边，建议看完想像以後再给自己一次机会试一次。

程序码撰写

class Solution:
    def Triplets(self, record_triplet, count, list, a, b, c, startIdx = 0):
        # 确认是否符合 |arr[i] - arr[j]| <= a
        if len(record_triplet) == 2 and not (abs(record_triplet[0] - record_triplet[1]) <= a): return count
        # 确认是否符合 |arr[j] - arr[k]| <= b
        # 确认是否符合 |arr[i] - arr[k]| <= c
        # 以上三个都符合会将 count + 1 ， count为符合条件的总数
        if len(record_triplet) == 3:
            if (abs(record_triplet[1] - record_triplet[2]) <= b
            and abs(record_triplet[0] - record_triplet[2]) <= c):
                count += 1
            return count
        
        # record_triplet 是一个 Stack，用来存放三个数的总和
        for i in range(startIdx, len(list)):
            # 若发现已经无法组成三个数组合，直接结束
            if len(record_triplet) == 0 and startIdx >= len(list) - 2: break
            if len(record_triplet) == 1 and startIdx >= len(list) - 1: break
            # 每一圈放一个值，处理完拿出来
            record_triplet.append(list[i])
            count = self.Triplets(record_triplet, count, list, a, b, c, i+1)
            record_triplet.pop()
        # 回传目前符合条件的总数
        return count
    
    def countGoodTriplets(self, arr: List[int], a: int, b: int, c: int) -> int:
        return self.Triplets([], 0, arr, a, b, c)

希望您今天能了解到...

1. Enumeration 基本概念
2. 1534. Count Good Triplets 的解题方法

若内容有什麽问题或建议欢迎一起交流：）
感谢您今天愿意花时间看完这篇文章~~~~

Next：1566. Detect Pattern of Length M Repeated K or More Times