974. Subarray Sums Divisible by 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)$