題目資訊

• 題目編號: 1534
• 題目連結: Count Good Triplets
• 主題: Array, Enumeration

題目敘述

給定一個整數陣列 arr，以及三個整數 a，b 和 c。你需要找到「好三元組」的數量。

如果一個三元組 (arr[i], arr[j], arr[k]) 滿足以下條件，則其為好的：

• $0 \leq i < j < k < arr.length$
• $|arr[i] - arr[j]| \leq a$
• $|arr[j] - arr[k]| \leq b$
• $|arr[i] - arr[k]| \leq 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 \leq arr.length \leq 100$
• $0 \leq arr[i] \leq 1000$
• $0 \leq a, b, c \leq 1000$

直覺

這個問題要求我們在數組中識別滿足某些絕對差值條件的三元組。這些條件對選擇索引 $(i, j, k)$ 進行了限制，使得 $0 \leq i < j < k < arr.length$。主要的直覺是遍歷數組中所有可能的三元組組合，並根據給定的條件驗證它們。為了有效地解決這個問題，我們應該專注於一種系統化的方法，以最小化重複並確保所有條件都得到檢查。

解法

該算法使用三層嵌套迴圈的直接方法來生成所有可能的三元組 $(arr[i], arr[j], arr[k])$。以下步驟詳細描述了解決方法：

1. 初始化計數器：首先將 goodTripletCount 初始化為零。這個計數器將追蹤滿足指定條件的三元組數量。

2. 選擇第一個元素的迴圈：使用迭代器 i 的第一個迴圈來選擇三元組的第一個元素。該迴圈從0運行到 arr.size() - 2，以確保至少有兩個剩餘元素可用於後續索引。

3. 選擇第二個元素的迴圈：在第一個迴圈中，使用迭代器 j 的第二個迴圈，範圍是從 i + 1 到 arr.size() - 1。這保證了 $j$ 永遠大於 $i$，維持所需的順序。

4. 檢查第一個條件：在選擇第三個元素之前，檢查 arr[i] 和 arr[j] 之間的絕對差是否小於等於 $a$。如果不滿足，則跳過此次 $j$ 的迭代。

5. 選擇第三個元素的迴圈：如果滿足第一個條件，使用迭代器 k 的第三個迴圈，範圍是從 j + 1 到 arr.size()。這確保 $k$ 永遠大於 $j$。

6. 檢查剩餘條件：對於每個三元組 $(i, j, k)$，檢查條件 $|arr[j] - arr[k]| \leq b$ 和 $|arr[i] - arr[k]| \leq c$。如果兩個條件都成立，則增加 goodTripletCount。

7. 返回計數：在所有迴圈運行結束後，返回 goodTripletCount 作為結果，這表示有效的三元組數量。

這種方法利用了一種直接但耗費的搜尋，針對於輸入數組的限制大小，確保所有可能的組合在沒有不必要計算的情況下得到評估。這個問題的限制和數組的大小使得此方法在計算上是可行的。

程式碼

C++

class Solution {
public:
    int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
        int goodTripletCount = 0;
        
        // 遍歷陣列以選取三元組的第一個元素
        for (int i = 0; i < arr.size() - 2; i++) {
            // 遍歷以選取三元組的第二個元素
            for (int j = i + 1; j < arr.size() - 1; j++) {
                // 檢查 arr[i] 和 arr[j] 之間的絕對差是否在限制 a 之內
                if (abs(arr[j] - arr[i]) > a) continue;
                
                // 遍歷以選取三元組的第三個元素
                for (int k = j + 1; k < arr.size(); k++) {
                    // 同時檢查 arr[j] 和 arr[k] 及 arr[i] 和 arr[k] 的條件
                    if (abs(arr[k] - arr[j]) <= b && abs(arr[k] - arr[i]) <= c) {
                        goodTripletCount++;
                    }
                }
            }
        }
        
        return goodTripletCount;
    }
};

Python

class Solution:
    def countGoodTriplets(self, arr, a, b, c):
        goodTripletCount = 0

        # 遍歷陣列以選擇三元組的第一個元素
        for i in range(len(arr) - 2):
            # 遍歷以選擇三元組的第二個元素
            for j in range(i + 1, len(arr) - 1):
                # 檢查 arr[i] 和 arr[j] 之間的絕對差是否在限制 a 以內
                if abs(arr[j] - arr[i]) > a:
                    continue
                
                # 遍歷以選擇三元組的第三個元素
                for k in range(j + 1, len(arr)):
                    # 檢查 arr[j] 和 arr[k] 以及 arr[i] 和 arr[k] 的兩個條件
                    if abs(arr[k] - arr[j]) <= b and abs(arr[k] - arr[i]) <= c:
                        goodTripletCount += 1

        return goodTripletCount

複雜度分析

• 時間複雜度: $O(n^3)$ 給定的程式碼使用三層嵌套迴圈遍歷陣列以選擇三元素組合：

  1. 最外層的迴圈遍歷陣列以選擇三元素組合的第一個元素。它大約運行 $n-2$ 次，其中 $n$ 是陣列的長度。
  2. 中間的迴圈用來選擇三元素組合的第二個元素，對於外層迴圈的每次迭代，它大約運行 $n-1-i$ 次。
  3. 最內層的迴圈選擇三元素組合的第三個元素，對於每對 i 和 j，它大約運行 $n-j$ 次。

  這些迴圈中的每一個都對總體時間複雜度貢獻了一個因子，從而導致總體複雜度為 $O(n^3)$。鑑於陣列的長度限制是最多100，這一立方複雜度在問題的限制範圍內是可行的。

• 空間複雜度: $O(1)$ 無論輸入大小如何，該演算法都使用固定量的額外空間。該演算法使用的空間主要由整數 goodTripletCount 和迴圈的控制變數（i、j 和 k）定義。因此，空間複雜度是固定的，$O(1)$。