[python 刷题] 974 Subarray Sums Divisible by K

本文主要是介绍[python 刷题] 974 Subarray Sums Divisible by K，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[python 刷题] 974 Subarray Sums Divisible by K

题目如下：

Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.

A subarray is a contiguous part of an array.

依旧是 prefix sum 的变种题，基础技巧，即使用 hashmap 去保存 prefix sum 的这个特性与 [JavaScript 刷题] 哈希表 - 和为 K 的子数组, leetcode 560 的核心技巧一致，不过这里保存的并不是当前的前缀和，而是余数。

其利用的特性是当出现两个以上，余数为一样的子数组，自然代表着中间的前缀和为可被 $k$ 所整除

以题目 [4,5,0,-2,-3,1] 为例，遍历过程如下：

1. 
2. 
3. 
4. …

以余数为 4 的例子来说，它其实可以视作穷举所有余数为 4 所可能存在的组合：

这也对应的存在的这几个结果：

4 -> 5 对应 [5]

4 -> 0 对应 [5, 0]

4 -> -3 对应 [5, 0, -2, -3]

5 -> -3 对应 [0, -2, -3]

0 -> -3 对应 [-2, -3]

可以看到，数组中余数为 4 出现了 4 次，其组合可以呗写为 $3+2+1$，将 4 视作 $n$ 的话，也就是 $n+(n-1)+(n-2)+...+2+1$，最终可以被简化为 $\frac{n(n-1)}{2}$

随后再加上子数组和为 $0$，也就是数组的和本身就可以被 k 所整除的个数，最终就能够得到结果

python 代码如下：

class Solution:def subarraysDivByK(self, nums: List[int], k: int) -> int:remainders = Counter(map(lambda x: x % k, accumulate(nums)))ans = 0for r in remainders:# combinations of prefixes have same remainer mod kans += remainders[r] * (remainders[r]-1) // 2ans += remainders[0]return ans

这篇关于[python 刷题] 974 Subarray Sums Divisible by K的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---