題目資訊

• 題目編號: 3392
• 題目連結: Count Subarrays of Length Three With a Condition
• 主題: Array

題目敘述

給定一個整數數組 nums，返回長度為 3 的子數組數量，其中第一個和第三個數字的和恰好等於第二個數字的一半。

範例 1:

• 輸入: nums = [1,2,1,4,1]
• 輸出: 1
• 解釋:
  只有子數組 [1,4,1] 恰好包含 3 個元素，其中第一個和第三個數字的和等於中間數字的一半。

範例 2:

• 輸入: nums = [1,1,1]
• 輸出: 0
• 解釋:
  [1,1,1] 是唯一一個長度為 3 的子數組。然而，其第一個和第三個數字的和不等於中間數字的一半。

約束條件:

• $3 \leq \text{nums.length} \leq 100$
• $-100 \leq \text{nums}[i] \leq 100$

直覺

這個問題要求計算所有長度為3的子陣列，其中第一個元素和第三個元素的和正好等於中間元素的一半。考量到題目限制，可以推測使用暴力解法是可行的。基本的直覺是遍歷所有可能的子陣列，檢查指定的條件。因為題目限定了子陣列正好包含三個元素，因此解法上較為簡單。

解法

首先，我們初始化一個計數器變數為零，這個變數將用來儲存符合條件的子陣列數量。接著，我們以索引 $i$ 遍歷陣列，使得每次都考慮從索引 $i$ 到 $i+2$ 的子陣列。迴圈會在 $length - 2$ 結束，以防止存取到超出陣列邊界的索引。

對於每一個子陣列 $nums[i]$, $nums[i+1]$, $nums[i+2]$，我們檢查條件：$$2 \times (nums[i] + nums[i+2]) = nums[i+1]$$。這個條件確保第一個和第三個元素的和等於中間元素的一半。如果該條件被滿足，計數器即自增一。遍歷整個陣列後，計數器現在包含了所有符合條件的子陣列數量，最後將該值返回。

這個方法有效地處理了給定的約束條件，以線性時間遍歷陣列，並檢查每個三連串數字組合的條件。

程式碼

C++

class Solution {
public:
    int countSubarrays(vector<int>& nums) {
        int count = 0;
        int length = nums.size();

        // 遍歷陣列，考慮每組連續的3個元素
        for (int i = 0; i < length - 2; i++) {
            // 檢查第一個和第三個數字的和是否等於第二個數字的一半
            if (2 * (nums[i] + nums[i + 2]) == nums[i + 1]) {
                count++; // 如果條件滿足則遞增計數
            }
        }
        return count; // 返回有效子陣列的總數
    }
};

Python

class Solution:
    def countSubarrays(self, nums):
        count = 0
        length = len(nums)

        # 迭代整個數組，考慮每組連續的三個元素
        for i in range(length - 2):
            # 檢查第一個和第三個數的和是否等於第二個數的二分之一
            if 2 * (nums[i] + nums[i + 2]) == nums[i + 1]:
                count += 1  # 如果條件滿足則計數加一
        
        return count  # 返回有效子陣列的總數量

複雜度分析

• 時間複雜度: 該演算法的時間複雜度為 $O(n)$，其中 $n$ 是輸入陣列 nums 的長度。這是因為演算法僅對陣列進行一次迭代，每個長度為 3 的可能子陣列只檢查一次。

• 空間複雜度: 演算法的空間複雜度為 $O(1)$。演算法使用恆定量的附加空間，與輸入大小無關，用於像 count 和 length 這類變數。