# [974\. Subarray Sums Divisible by K](https://leetcode.com/problems/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;
    }
};

:::success
- 時間複雜度：$O(n + k)$
- 空間複雜度：$O(n)$
:::