Leetcode - subarray-sums-divisible-by-k

Input: A = [4,5,0,-2,-3,1], K = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by K = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

The solution is similar to this one, using preSum map Leetcode - subarray-sum-equals-k

func subarraysDivByK(A []int, K int) int {
    preSum := map[int]int{
        0: 1,
    }
    count := 0
    sum := 0
    for _, a := range A {
        sum = (sum + a)%K
        if sum < 0 {
            sum += K
        }
        count += preSum[sum]
        preSum[sum]++
    }
    
    return count
}

# @param {Integer[]} a
# @param {Integer} k
# @return {Integer}
def subarrays_div_by_k(a, k)
    pre_sum = {}
    pre_sum[0] = 1
    count = 0
    sum = 0
    a.each do |val|
        sum = (sum + val)%k
        if sum < 0 
            sum += k
        end
        pre_sum[sum] = 0 if pre_sum[sum].nil?
        count += pre_sum[sum]
        pre_sum[sum] += 1
    end
    return count
end

• 相关文章
• 全局相关文章