【LeetCode】974.和可被k整除的子数组

题目

思路

思路一
暴力破解，两层循环，判断每个子数组能够被k整除。

思路二
前缀和。

因此，只要根据当前第j个数结尾的数组之和 的模，去找之前前缀模相同的数量，即为可被k整数的子区间的数量。
因为与mod k，余数只可能有k-1中有限情况。（比如mod 3，余数只可能有0,1,2）
所以用哈希表去维护余数modulus时，连续子区间的数量。

看代码

代码

暴力破解代码，优化求和

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        n = len(A)
        if not any(A):
            # 全零
            return int(n*(n+1)*0.5)
        tmp = []
        cum = []
        count = 0
        cum_sum = 0
        for num in A:
            cum.append(num)
            cum_sum += num
            tmp = cum[:]
            tmp_sum = cum_sum
            while tmp:
                if tmp_sum % K == 0:
                    count += 1
                tmp_sum -= tmp.pop(0)
        return count

时间超了，通过不了全部测试用例。

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        record = {0: 1}
        total, ans = 0, 0
        for elem in A:
            total += elem # 当前elem结尾的区间之和
            modulus = total % K # 求模
            same = record.get(modulus, 0) # 得到之前模相同的子区间的个数
            ans += same # 计数器增加
            record[modulus] = same + 1 # 维护哈希表
        return ans