【974】和可被 K 整除的子数组：中等

https://leetcode-cn.com/problems/subarray-sums-divisible-by-k/ 数组，哈希表

数组遍历

直接想到的，但是超时

function subarraysDivByK(A: number[], K: number): number {
    const len = A.length
    if (!len) return 0
    let i = 1
    let res = 0
    while (i <= len) {
        let l = 0
        let r = i
        while (r <= len) {
            let add = A.slice(l, r).reduce((a, b) => a + b)
            if (add % K === 0) res++
            l++
            r++
        }
        i++
    }
    return res
};

哈希表

利

/* 
let A = [4,5,0,-2,-3,1], K = 5
let map = {0: 1}
let preSum = 0, count = 0

循环A
i = 0,  preSum = (0 + 4) % 5 = 4, map中不存在4 => map[4] = 1
i = 1,  preSum = (4 + 5) % 5 = 4, map中存在4 => count += map[4] => count = 1,  map[4] = map[4] + 1 = 2
i = 2,  preSum = (4 + 0) % 5 = 4, map中存在4 => count += map[4] => count = 3,  map[4] = 3
i = 3,  preSum = (4 - 2) % 5 = 2, map中不存在2 => map[2] = 1
i = 4,  preSum = (2 - 3) % 5 = -1 小于0 => preSum = -1 + 5 = 4, map中存在4 => count += map[4] => count = 6,  map[4] = 4
i = 5,  preSum = (4 + 1) % 5 = 0, map中存在0 => count += map[0] => count = 7, map[0] = 2
*/

function subarraysDivByK(A: number[], K: number): number {
    let len = A.length
    let map = {0: 1}
    let presum = 0
    let res = 0

    for (let i = 0; i < A.length; i++) {
        presum = (presum + A[i]) % K
        if (presum < 0) {
            while (presum < 0) {
                presum += K
            }
        }
        if (map[presum]) {
            res += map[presum]
            map[presum]++
        } else {
            map[presum] = 1
        }
    }

    return  res
};