

LeetCode: 974. 和可被 K 整除的子数组

• LeetCode: 974. 和可被 K 整除的子数组
  • 1、题目描述
  • 2、解题思路

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$

2、解题思路

• 使用取余的方式判断

• 如果中间一段能够整除5，那么这两个位置的前缀和对于K取余数肯定是相同的

• 根据余数相同的数量，这一段组成的数量为x*(x-1)//2

from collections import defaultdict


class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        d = defaultdict(int)
        d[0] = 1
        sums = 0
        for num in A:
            sums = (sums + num) % K
            d[sums] += 1


        return sum([x * (x - 1) // 2 for x in d.values()])