974. Subarray Sums Divisible by K

O(n) time O(n) space
统计模K同余的presum，跟523. Continuous Subarray Sum类似，区别是K是正数且array可能有负数，所以不需要非得给前缀和维护一个hashmap，直接开一个长度为K的数组来统计即可

class Solution {
public:
    int subarraysDivByK(vector<int>& A, int K) {
        int n = A.size();
        vector<int> cnt(K);
        cnt[0] = 1; // 必须初始化模0的个数为1，表示什么都没有的情况有1个！！
        for (int i = 0, p = 0; i < n; ++i) {
            p += A[i];
            ++cnt[((p % K) + K) % K];
        }
        int res = 0;
        for (int x : cnt) {
            res += x * (x - 1) / 2; // 即(x - 1) * ((x - 1) + 1) / 2
        }
        return res;
    }
};

O(n²) time O(n) space

class Solution {
public:
    int subarraysDivByK(vector<int>& A, int K) {
        int n = A.size();
        vector<int> presum(n + 1);
        for (int i = 0; i < n; ++i) {
            presum[i + 1] = presum[i] + A[i];
        }
        int res = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                int t = (presum[j] - presum[i]) % K;
                res += t == 0;
            }
        }
        return res;
    }
};