LeetCodeブラシノート974:とKで割り切れるサブ配列(Python実装)

タイトルの説明:
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]

  ：

1 <= A.length <= 30000

-10000 <= A[i] <= 10000

2 <= K <= 10000

LeetCode 560:Kのサブ配列とよく似ていますが、if判定条件を修正するだけですSolution1： ， O(N^2) ，

class Solution:
    def subarraysDivByK(self,A,K):
        '''
        
        :type A: List[int]
        :type K: int
        :rtype: int
        '''
        count = 0
        for i in range(len(A)):
            sum = 0
            for j in range(i,len(A)):
                sum+=A[j]
                if sum % K == 0:
                    count+=1
        return count

Solution2:
サブ配列がKで除去されるかどうかを見る以上、count_を設定することができます.mod_i = (A[0] + A[1] + A[2] +·······+A[i])%K,count_mod_j=(A[0]+A[1]+A[2]+・・+A[i]+A[i+1]+・・+A[j])%K、ここでj>i、count_mod_j - count_mod_i=0であれば、A[i]からA[j]までのサブ配列は必ずKで割り切れる.
A=[4,5,0,-2,-3,1],K=5.
1番目の数、すなわちA[0]=4は、i=0、すなわちA[0]の和のみを算出し、その後、Kを模演算する:A[0]%5=4、次いでj=1、すなわち2番目の数A[1]は、A[0]からA[1]の和を計算した後、模演算を行う:(A[0]+A[1])%5=4であり、両者は等しい(これは1つの場合である)、これは、A[0]からA[1]の間のサブ配列とA[1]が5で割り切れることを示し、事実は、A[1]=5が確かに5で割り切れることを証明している.そして、このすべての状況(同じ余数の回数)をそれぞれ記録します.得られた剰余が4の回数が1であれば,この場合の子数列の個数だけで1*(1−1)/2=0となるのは,一度しか現れない(剰余が4)ため,最初に我々が言ったような考えには合致しない.得られた剰余数が4の回数が2であれば,この場合に限ってサブ数列の個数は2*(2−1)/2=1となる.最後にすべての状況を加算
コード:

import collections

class Solution:
    
    def subarraysDivByK(self,A,K):
        '''
        :param A: list[int]
        :param K: int
        :return: int
        '''
        count_mod = [0]
        for num in A:
            count_mod.append((count_mod[-1]+num) % K)
    
        count = collections.Counter(count_mod)
        return sum((v-1)*v/2 for v in count.values())