題目資訊

• 題目編號: 2302
• 題目連結: Count Subarrays With Score Less Than K
• 主題: Array, Binary Search, Sliding Window, Prefix Sum

題目敘述

The score of an array is defined as the product of its sum and its length.

• 例如，$$1, 2, 3, 4, 5$$ 的分數是 $(1 + 2 + 3 + 4 + 5) \times 5 = 75$。

給定一個正整數數組 nums 和一個整數 k，返回 數組 nums 中分數 嚴格小於 k 的非空子數組的數量。

一個 子數組 是數組中連續的一段元素序列。

範例 1:

• 輸入: nums = [2,1,4,3,5], k = 10

• 輸出: 6

• 解釋:
  分數小於 10 的 6 個子數組是：

  • [2] 的分數是 $2 \times 1 = 2$。
  • [1] 的分數是 $1 \times 1 = 1$。
  • [4] 的分數是 $4 \times 1 = 4$。
  • [3] 的分數是 $3 \times 1 = 3$。
  • [5] 的分數是 $5 \times 1 = 5$。
  • [2,1] 的分數是 $(2 + 1) \times 2 = 6$。

  注意，像 [1,4] 和 [4,3,5] 這樣的子數組不被考慮，因為它們的分數分別是 10 和 36，而我們需要分數嚴格小於 10。

範例 2:

• 輸入: nums = [1,1,1], k = 5
• 輸出: 5
• 解釋:
  除了 [1,1,1] 之外的每個子數組的分數都小於 5。
  [1,1,1] 的分數是 $(1 + 1 + 1) \times 3 = 9$，這大於 5。
  因此，有 5 個子數組的分數小於 5。

約束條件:

• $1 \leq \text{nums.length} \leq 10^5$
• $1 \leq \text{nums}[i] \leq 10^5$
• $1 \leq k \leq 10^{15}$

直覺

此問題涉及尋找一個給定的整數陣列中，所有子陣列的數量，其中子陣列的分數定義為其和與其長度的乘積，且該分數必須嚴格小於給定整數 $k$。由於約束條件允許陣列的長度及其元素的值相當大（可達到 $10^5$），因此需要一種高效的方法來在合理的時間內解決這個問題。暴力搜索所有可能的子陣列並計算它們的分數將因其潛在的二次時間複雜性而在計算上是不可行的。

為了解決這個問題，我們可以使用雙指針或滑動窗口技術，這個技術會動態計算子陣列的元素和，並調整其邊界以保持合法的分數。此方法通過維持一個持續更新的和並動態調整窗口尺寸，從而避免冗餘計算，使其更加高效。

解法

解決方案採用了滑動窗口方法，這個方法使用兩個指針標記當前子陣列的開始和結束。主要步驟如下：

1. 初始化變數：

   • totalSubarrays 用來計數合法的子陣列。
   • currentSum 存儲當前子陣列的和。
   • left 作為當前子陣列窗口的起始指針。

2. 遍歷陣列：

   • 使用一個 right 指針遍歷陣列的每一個元素，作為當前子陣列的結束。
   • 對於每一個元素 nums[right]，將其值加到 currentSum 中。

3. 調整滑動窗口：

   • 當當前子陣列的分數（currentSum * (right - left + 1)）大於或等於 $k$ 時，通過從 currentSum 中移除索引 left 的元素並遞增 left 指針來減小窗口尺寸。這確保子陣列的分數保持小於 $k$。

4. 計數有效子陣列：

   • 在調整窗口後，所有以 right 為結束且起始點由 left 到 right 的子陣列均為合法。因此，將 totalSubarrays 加上 right - left + 1。

5. 返回結果：

   • totalSubarrays 累計了整個遍歷過程中所有合法子陣列的數量，最終作為結果返回。

這種方法使得每個元素最多被評估兩次（由於 right 指針向前移動以及 left 指針也可能向前移動以調整窗口），時間複雜度為 $O(n)$，其中 $n$ 是陣列的長度。這保證了解法能夠在合理的計算限制內處理大型輸入數據。

程式碼

C++

class Solution {
public:
    long long countSubarrays(vector<int>& nums, long long k) {
        long long totalSubarrays = 0; // 用於儲存分數小於 k 的子陣列的計數
        long long currentSum = 0;     // 儲存當前子陣列的總和
        long long arrayLength = nums.size(); // 輸入陣列的長度
        long long left = 0;           // 滑動窗口的左指標
        
        // 使用右指標遍歷陣列，形成子陣列的結尾
        for (long long right = 0; right < arrayLength; right++) {
            currentSum += nums[right]; // 將當前元素加入子陣列總和
            
            // 檢查子陣列分數是否不小於 k，如是則調整左邊界
            while (currentSum * (right - left + 1) >= k) {
                currentSum -= nums[left]; // 從總和中移除左指標的元素
                left++;                   // 移動左指標以縮小窗口
            }
            
            // 加上以 `right` 為結尾的有效子陣列數量
            totalSubarrays += right - left + 1;
        }
        
        return totalSubarrays;
    }
};

Python

class Solution:
    def countSubarrays(self, nums, k):
        totalSubarrays = 0  # 用於儲存分數小於 k 的子陣列數量的變數
        currentSum = 0      # 儲存當前子陣列的總和
        arrayLength = len(nums)  # 輸入陣列的長度
        left = 0            # 滑動窗口的左指標
        
        # 遍歷陣列，右指標形成子陣列的結尾
        for right in range(arrayLength):
            currentSum += nums[right]  # 將當前元素加入子陣列總和
            
            # 檢查子陣列分數是否不小於 k，調整左邊界
            while currentSum * (right - left + 1) >= k:
                currentSum -= nums[left]  # 從總和中移除左邊的元素
                left += 1                 # 移動左指標以縮小窗口
            
            # 添加以 `right` 為結尾的有效子陣列數量
            totalSubarrays += right - left + 1
        
        return totalSubarrays

複雜度分析

• 時間複雜度: $O(n)$
  該演算法使用滑動窗口技術和兩個指針 left 和 right，其中 right 精確地遍歷整個數組一次，而 left 逐步移動。因此，循環內的操作總數與數組的大小成正比，導致時間複雜度為 $O(n)$，其中 $n$ 是 nums 的長度。
• 空間複雜度: $O(1)$
  空間複雜度為 $O(1)$，因為該解決方案只使用固定數量的額外空間，且不會隨著輸入大小變化。像 totalSubarrays、currentSum 等變量消耗的空間是恆定的，與輸入數組大小無關。