# LeetCode 974. Subarray Sums Divisible by K

https://leetcode.com/problems/subarray-sums-divisible-by-k/description/

## 題目大意

給定整數陣列 `nums` 跟整數 `k` ，試問有多少非空子陣列其元素和可以被 `k` 整除？

## 思考

$O(n^2)$ 的暴力解就不提了，這邊直接快進到 $O(n)$ 的想法
想法依舊跟 prefix sum 有關，因為我們不是要求有哪些符合題意的子陣列，我們只求有幾個，所以直接操控總和即可

想法就是我們查看所到之處為結尾的子陣列總和，每次先檢查從頭到尾總和能不能被 `k` 整除並記錄餘數

餘數就 `k` 種，也就是 `0` 到 `k-1`，所以我們用個 vector `cnt` 來記錄就好

`cnt[0]` 可想而知一定會被加進 `ans` 中，那麼其他餘數記錄要幹嘛？

當我們走到 `nums[i]` 時，假設此時 $\sum\limits_{i=0}^{i}\mathrm{nums}[i] = \mathrm{sum}_i$ 且 $\mathrm{sum}_i \mod k = r$
我們看到 `nums[i]` 之前有出現幾次 prefix sum 為 `r` ，將當前總和扣掉 `r` 為題意所求，那麼 `cnt[r]` 有幾次就代表有幾種可能可以扣掉 `r`

class Solution
{
public:
    int subarraysDivByK(vector<int> &nums, int k)
    {
        int ans = 0;
        int sum = 0;
        vector<int> cnt(k);
        cnt.front() = 1;

        for (const int num : nums)
        {
            sum += num;
            int remain = sum % k;
            if (remain < 0)
                remain += k;
            ans += cnt[remain]++;
        }

        return ans;
    }
};

值得注意的是， `nums` 中的數字並未說不可以是負數，故有可能總和當前是負的，那麼 `remain` 也會是負的

例如 73 筆測資中的第 3 筆就會遇到問題：

Testcase:
- `nums = [-2]`
- `k = 6`

所以要檢查 `remain` 是否為負的，如果他是負的就把他加 `k` 回去

我一開始寫完沒想到這部分，就 Runtime Error 了😅