leetcode第九百七十四题—和可被 K 整除的子数组
2020-03-11 本文已影响0人
不分享的知识毫无意义
你可能会疑惑我的简书更新怎么这么乱,因为我是一个随性的人,现在对数组感兴趣就多做点数组的题。
1.题目
原题
给定一个整数数组 A,返回其中元素之和可被 K 整除的(连续、非空)子数组的数目。
例子
输入:A = [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.解析
这道题,最开始的思路就是双指针,但是双指针的思路,最后还是会超时,按照leetcode一贯的思路,应该有个巧妙的推演,于是产生了思路2。
思路1:双指针,初始和结束指针都指向0然后开始计算,遇到整除的count就加1,然后就是设置初始指针和结束指针的更新方法。具体看代码吧。
思路2:归纳法,这道题其实就是说如果到i的和以及到j的和除以k余数相同,他们中间的任意一种组合都是都可以被k整除,怎么解释呢,就是中间只有除完K取余数为0,才可以算出相同的结果。然后两两组合吗,就用x*(x-2)//2就计算出最后的数了。
这里python有个collection模块,可以对数组进行统计,在文本处理中应用非常多的。
3.python代码
##双指针法,和暴力求解法差不多
def subarraysDivByK(self, A, K):
start, end = 0, 0
n = len(A)
tmpsum = 0
count = 0
# if n == 1 and A[0] % K == 0:
# count = 1
# else:
# count = 0
while start < n and end < n:
tmpsum = sum(A[start:end+1])
if tmpsum % K == 0:
print(start, end)
count += 1
end += 1
else:
end += 1
if end == n:
start += 1
end = start
return count
##归纳法
def subarraysDivByK(self, A, K):
import collections
AmodK = [0]
for i in range(len(A)):
# print(i)
AmodK.append((AmodK[-1]+A[i]) % K)
AmodK = collections.Counter(AmodK)
# print(AmodK.items())
return sum((x*(x-1)//2 for x in AmodK.values()))