LeetCode-Python-974. Kで割り切れるサブ配列と

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

 
考え方:
テーマは連続するサブ配列の和がKによって整除されることを求めて、連続するサブ配列の和は接頭辞の和の差として表すことができて、
例えばsum(A[i:j+1])=s[j+1]-s[i]であり、2つの数の差がKで割り切れる場合、この2つの数modKで得られた結果が同じであることを示し、modkに対して同じ数がどれだけあるかを探せば結果が得られる.例えば、A=[4,5,0,-2,-3,1]K=5,s=[0,4,9,9,7,4,5]であり、kcnt=[2,0,1,0,4]は、s中の2つの要素の残数がいずれも0(すなわち0と5)、1つの要素の残数が2(すなわち7)、4つの要素の残数が4(すなわち4994)であることを表すので、残数が同じであることを保証する場合、2つの数を取り出しても1組の答えを得ることができる.この例の答えはC 22+C 12+C 42=1+0+6=7です

class Solution(object):
    def subarraysDivByK(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: int
        """
        s = [0 for i in range(len(A) + 1)] #s     ， s[i]  sum(A[:i])
        kcnt = [0 for i in range(K)] #kcnt[i]  s        mod K  i
        for i in range(len(A)):
            s[i + 1] = s[i] + A[i]
        for item in s:
            kcnt[item % K] += 1
        #print s, kcnt

        return sum(x * (x - 1) // 2 for x in kcnt)