今日題目

題目連結：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