題目資訊

• 題目編號: 2845
• 題目連結: Count of Interesting Subarrays
• 主題: Array, Hash Table, Prefix Sum

題目敘述

你得到一個0-索引的整數數組 nums，一個整數 modulo，以及一個整數 k。

你的任務是找出被稱為有趣的子陣列的數量。

如果滿足以下條件，則子陣列 nums[l..r] 是有趣的：

• 令 cnt 為範圍 [l, r] 中滿足 nums[i] % modulo == k 的索引 i 的數量。然後，cnt % modulo == k。

返回一個整數，表示有趣子陣列的數量。

注意： 子陣列是數組中連續的非空元素序列。

範例 1:

輸入: nums = [3,2,4], modulo = 2, k = 1
輸出: 3
解釋: 在此範例中，有趣的子陣列為： 
子陣列 nums[0..0] 即 [3]。
- 僅有一個索引，即 i = 0，在範圍 [0, 0] 中滿足 nums[i] % modulo == k。
- 因此，cnt = 1 且 cnt % modulo == k。  
子陣列 nums[0..1] 即 [3,2]。
- 僅有一個索引，即 i = 0，在範圍 [0, 1] 中滿足 nums[i] % modulo == k。  
- 因此，cnt = 1 且 cnt % modulo == k。
子陣列 nums[0..2] 即 [3,2,4]。 
- 僅有一個索引，即 i = 0，在範圍 [0, 2] 中滿足 nums[i] % modulo == k。
- 因此，cnt = 1 且 cnt % modulo == k。 
可以證明沒有其他有趣的子陣列。所以，答案是 3。

範例 2:

輸入: nums = [3,1,9,6], modulo = 3, k = 0
輸出: 2
解釋: 在此範例中，有趣的子陣列為： 
子陣列 nums[0..3] 即 [3,1,9,6]。
- 在範圍 [0, 3] 中有三個索引滿足 nums[i] % modulo == k，即 i = 0, 2, 3。 
- 因此，cnt = 3 且 cnt % modulo == k。
子陣列 nums[1..1] 即 [1]。
- 在範圍 [1, 1] 中沒有索引滿足 nums[i] % modulo == k。
- 因此，cnt = 0 且 cnt % modulo == k。 
可以證明沒有其他有趣的子陣列。所以，答案是 2。

約束條件：

• $1 \leq nums.length \leq 10^5$
• $1 \leq nums[i] \leq 10^9$
• $1 \leq modulo \leq 10^9$
• $0 \leq k < modulo$

直覺

這個問題要求識別在給定整數陣列中符合特定模算術條件的子陣列。乍看之下，我們可能會考慮生成所有可能的子陣列並檢查其是否滿足條件。然而，由於組合爆炸，此方法在計算上會非常昂貴。取而代之的是，認識到這是一個涉及前綴和與模算術問題，可以得出一個更有效的解決方案。這個想法是利用前綴和以動態跟蹤陣列中的條件，而不需要重複計算每個可能的子陣列。

解法

為了有效地解決這個問題，我們使用前綴和結合模算術的概念。此方法的主要元素如下：

1. 帶模的前綴和： 我們維護一個 prefix_sum，表示到目前索引為止，數字模以 modulo 後等於 k 的計數。通過將此計數表示為前綴和，我們可以有效地計算任何以當前索引結尾的子陣列的條件。

2. 用哈希表計算前綴出現次數： 我們使用一個無序映射 mod_map 來跟蹤到目前位置為止，每個可能的 prefix_sum % modulo 值出現的次數。這允許我們快速計算在當前位置結尾的有趣子陣列的數量，通過檢查形成有效子陣列的方法數。

3. 計算過程： 對於陣列中的每個元素：

   • 如果當前數字模以 modulo 後等於 k，則更新 prefix_sum。
   • 將 prefix_sum 模以 modulo 以確保它保持在邊界之內。
   • 檢查有多少前綴次數滿足條件 (prefix_sum - k + modulo) % modulo，這使得形成一個子陣列本身具有有趣條件。
   • 在映射中存儲當前的 prefix_sum 的出現。

4. 遍歷陣列： 此方法保證我們只考慮每個數字一次，通過利用前綴和與一個哈希映射來有效地計算結果，因此時間複雜度為線性 $O(n)$。

這種方法有效地跟蹤和計算有趣的子陣列，而不需對每個子陣列重複計算，從而優化時間複雜度至 $O(n)$。

程式碼

C++

class Solution {
public:
    // 計算有趣子陣列的數量的函式
    long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
        unordered_map<int, int> mod_map;  // 記錄每個前綴和 % modulo 出現次數的映射
        long long prefix_sum = 0;         // 儲存當前前綴和的模數
        long long interesting_count = 0;  // 儲存有趣子陣列的總數
        
        mod_map[prefix_sum]++;  // 初始化時將前綴和 0 的計數加一

        // 遍歷 nums 陣列中的每個數字
        for (int num : nums) {
            // 更新前綴和，並取模
            prefix_sum = (prefix_sum + (num % modulo == k)) % modulo;

            // 根據符合條件的先前前綴和增加計數
            interesting_count += mod_map[(prefix_sum - k + modulo) % modulo];

            // 將當前前綴和記錄在映射中
            mod_map[prefix_sum]++;
        }

        return interesting_count;  // 返回有趣子陣列的總數
    }
};

Python

class Solution:
    # 函數來計算有趣子陣列的數量
    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:
        mod_map = defaultdict(int)  # 記錄每個 prefix_sum % modulo 出現的次數的映射
        prefix_sum = 0  # 儲存目前前綴和的模數值的變數
        interesting_count = 0  # 儲存有趣子陣列總數的變數
        
        mod_map[prefix_sum] += 1  # 初始化時將前綴和0的計數加1

        # 遍歷 nums 陣列中的每個數字
        for num in nums:
            # 更新前綴和時，檢查條件，並取模
            prefix_sum = (prefix_sum + (num % modulo == k)) % modulo

            # 將符合條件的先前前綴和的數量加到計數中
            interesting_count += mod_map[(prefix_sum - k + modulo) % modulo]

            # 在映射中記錄目前的前綴和
            mod_map[prefix_sum] += 1

        return interesting_count  # 返回有趣子陣列的總數量

複雜度分析

• 時間複雜度: $O(n)$

  演算法針對 nums 陣列中的每個元素迭代一次，對於每個元素皆執行常數時間的操作。因此，時間複雜度與輸入陣列 $n$ 的大小呈線性關係。

• 空間複雜度: $O(\min(n, \text{modulo}))$

  演算法使用一個無序映射 mod_map 來存儲前綴和對 modulo 取餘數的計數。在最壞的情況下，由於前綴和取模運算得到的值處於 $[0, \text{modulo} - 1]$ 範圍內，映射最多可以有 $\min(n, \text{modulo})$ 個唯一的鍵，但這也受到元素數量 $n$ 的限制。因此，空間複雜度為 $O(\min(n, \text{modulo}))$。