974. Subarray Sums Divisible by K

子數列 [0, i] 的和子數列 [0, j] 的和，除以 k 的餘數相同的話，代表 [i + 1, j] 的和也可以被 k 整除。

舉個例子：nums = [1, 2, 3, 4]，k = 5

• 1 除以 5 餘 1
• [1, 2, 3] 除以 5，也餘 1

按照規律，[2, 3] 的和一定可以整除 5

也就是說，子數列能被 k 整除的關鍵是在餘數相不相同。

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k)
    {
        // 計算子數列能不能被 k 整除
        // sum[i : j] 能被 k 整除的條件就是
        // prefixSum[i] 和 prefixSum[j - 1] 除以 k 的餘數相同

     int res = 0, sum = 0;

        // 保存 prefixSum 除以 k 的餘數出現多少次
        unordered_map<int, int> m{{0, 1}};

        for (int num : nums)
        {
            // 累加 sum
            // 加上 k 的原因是確保結果為正整數
            // 沒有加上 k，有可能出現負數的情況
         sum = (sum + num % k + k) % k;

            // 加上相同餘數對應的頻率
         res += m[sum];

            // 餘數出現的頻率 + 1
         ++m[sum];
        }
        return res;
    }
};

• T: $O(n + k)$
• S: $O(n)$