和可被 K 整除的子数组

题目描述：

给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的（连续、非空） 子数组 的数目。

子数组 是数组的 连续 部分。

示例 1：

输入：nums = [4,5,0,-2,-3,1], k = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 k = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
示例 2:

输入: nums = [5], k = 9
输出: 0

提示:

1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
2 <= k <= 104
通过次数43,404提交次数92,342

思路:

时间复杂度：O(n),空间复杂度O(n)

使用map来优化前缀和的时间复杂度，注意点是防止前缀和为负值。

代码:

func subarraysDivByK(nums []int, k int) int {
    n := len(nums)
    if n==0{
        return 0
    }
    sum ,res := 0,0
    
    mp := make(map[int]int, 0)
    mp[0] = 1
    for i:= 0;i<n;i++{
        sum += nums[i]
        res += mp[((sum %k)+k)%k]
        mp[((sum %k)+k)%k]++
    }
    return res
}

代码效率：

执行用时：40 ms, 在所有 Go 提交中击败了89.63%的用户
内存消耗：6.7 MB, 在所有 Go 提交中击败了49.63%的用户