2845. 統計趣味子數組的數目

給你一個下標從 0 開始的整數數組 nums ，以及整數 modulo 和整數 k 。

請你找出并統計數組中 趣味子數組 的數目。

如果 子數組 nums[l..r] 滿足下述條件，則稱其為 趣味子數組 ：

在范圍 [l, r] 內，設 cnt 為滿足 nums[i] % modulo == k 的索引 i 的數量。并且 cnt % modulo == k 。
以整數形式表示并返回趣味子數組的數目。

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

示例 1：

輸入：nums = [3,2,4], modulo = 2, k = 1
輸出：3
解釋：在這個示例中，趣味子數組分別是：
子數組 nums[0..0] ，也就是 [3] 。

• 在范圍 [0, 0] 內，只存在 1 個下標 i = 0 滿足 nums[i] % modulo == k 。
• 因此 cnt = 1 ，且 cnt % modulo == k 。
  子數組 nums[0..1] ，也就是 [3,2] 。
• 在范圍 [0, 1] 內，只存在 1 個下標 i = 0 滿足 nums[i] % modulo == k 。
• 因此 cnt = 1 ，且 cnt % modulo == k 。
  子數組 nums[0..2] ，也就是 [3,2,4] 。
• 在范圍 [0, 2] 內，只存在 1 個下標 i = 0 滿足 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] 內，只存在 3 個下標 i = 0, 2, 3 滿足 nums[i] % modulo == k 。
• 因此 cnt = 3 ，且 cnt % modulo == k 。
  子數組 nums[1..1] ，也就是 [1] 。
• 在范圍 [1, 1] 內，不存在下標滿足 nums[i] % modulo == k 。
• 因此 cnt = 0 ，且 cnt % modulo == k 。
  可以證明不存在其他趣味子數組，因此答案為 2 。

提示：

解題思路：

見代碼注釋

code

class Solution {
public:

    /*
    綜合考察以下內容：前綴和 + 哈希表 + 數學

    1. 問題轉換 -> 前綴和
    nums[l,r]中nums[i] % m == k 的元素的數目cnt;
    如何快速查詢num[l,r]之間的cnt?前綴和
    區間查詢：前綴和
    區間更新：差分
    止步于此：如果遍歷所有的區間的時間復雜度依然是O(n ^ 2)

    2.兩數之和 -> 哈希表
    其實進一步思考得寫出前綴和計算公式
    前綴和需要在最前面補上一個0,那么nums[l,r]之間的和為：
    prefix[r + 1] - prefix[l]
    那么最后需要判斷的就是：
    (prefix[r + 1] - prefix[l]) % m == k
    也就是需要判斷：
    prefix[r + 1] % m - prefix[l] % m == k
    那這樣就簡單了：兩數之和，通過哈希表進行查找：
    已經知道右端點的值：prefix[r+1] - k,那么自然是在哈希表中查找prefix[l] % m

    3. 公式變形
    但是存在得到一個問題是：
    6 % 3 - 2 % 3 = -2
    (6 - 2) % 3 =  1
    大小關系發生了變化
    也就是實際上得有兩種情況：負數補上一個m
    (x - y) % 3 = x % 3 - y % 3
    (x - y) % 3 = x % 3 - y % 3 + 3
    綜合起來就是：


    不需要補上m:
    prefix[r + 1] % m - prefix[l] % m = k
    prefix[r + 1] % m - k = prefix[l] % m

    需要補上m:
    prefix[r + 1] % m - prefix[l] % m + m = k
    prefix[r + 1] % m - k + m = prefix[l] % m
    
    綜合起來就是：
    (prefix[r + 1] % m - k + m) % m = prefix[l] % m
    綜合的公式有點沒太看懂，但是不綜合起來也沒什么問題，無非就是判斷以下最終的結果負與非負罷了。

    公式推導曲折多變，不熟的話怎么能在有限緊張的時間里面寫出來呢？
    接下來就簡單：遍歷右端點，通過哈希表查詢左端點的數目。

    
    */        
    long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {

        int len = nums.size();

        vector<int> prefix(len + 1,0);

        for(int i = 0;i < nums.size();i ++)
        {
            if(nums[i] % modulo == k) prefix[i+1] = (prefix[i] + 1) % modulo;
            else prefix[i+1] = prefix[i];
        }
        
        long long int ans = 0;

        unordered_map<int,int> cnt;
        cnt[0] = 1;
        
        for(int right = 1;right < prefix.size();right ++)
        {
            int target = (prefix[right] - k + modulo) % modulo;
            auto it = cnt.find(target);

            if(it != cnt.end())
            {
                ans += it -> second;
            }

            cnt[prefix[right]] ++;
        }
        
        return ans;
        
    }
};

class Solution {
public:
    //優化掉前綴和數組        
    long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {

        int len = nums.size();

        //vector<int> prefix(len + 1,0);

        //for(int i = 0;i < nums.size();i ++)
        //{
        //    if(nums[i] % modulo == k) prefix[i+1] = (prefix[i] + 1) % modulo;
        //    else prefix[i+1] = prefix[i];
        //}
        
        long long int ans = 0;

        unordered_map<int,int> cnt;
        cnt[0] = 1;
        int prefix = 0;

        for(int i = 0;i < len;i ++)
        {
            if(nums[i] % modulo == k) prefix = (prefix + 1) % modulo;

            int target = (prefix - k + modulo) % modulo;
            auto it = cnt.find(target);

            if(it != cnt.end())
            {
                ans += it -> second;
            }

            cnt[prefix] ++;
        }
        
        return ans;
        
    }
};