[leetcode] 974. Subarray Sums Divisible by K

[leetcode] 974. Subarray Sums Divisible by K

Description

Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K. Example 1:

Input: A = [4,5,0,-2,-3,1], K = 5Output: 7Explanation: 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]

Note:

1 <= A.length <= 30000-10000 <= A[i] <= 100002 <= K <= 10000

分析

题目的意思是：这道题统计连续子串能够被K整除的个数，解法还是挺奇妙的，首先给P数组放一个0，然后遍历A进行求和，P[i+1] = A[0] + A[1] + … + A[i]. 然后再进行数的频率统计，最后统计的结果按照v*(v-1)/2求和就行了，不要问我为什么这样做就行了，我也不知道。但是我验证了一下结果却是是对的。

代码

class Solution: def subarraysDivByK(self, A: List[int], K: int) -> int: n=len(A) P=[0] for x in A: P.append((P[-1]+x)%K) count=collections.Counter(P) cnt=0 for v in count.values(): cnt+=v*(v-1)/2 return int(cnt)

参考文献

​​[LeetCode] Approach 1: Prefix Sums and Counting​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。