<jupyter_start><jupyter_text>说明：    给定一个整数数组 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、1 <= A.length <= 30000    2、-10000 <= A[i] <= 10000    3、2 <= K <= 10000<jupyter_code>from collections import Counter
class Solution:
    def subarraysDivByK(self, A, K: int) -> int:
        mod_val = []
        for a in A:
            if not mod_val:
                mod_val.append(a % K)
            else:
                val = (a % K + mod_val[-1]) % K
                mod_val.append(val)
                
        count = 0
        mod_val_dict = Counter(mod_val)
        print(mod_val_dict)
        N = len(A)
        for i in range(N):
            need_val_i = K - mod_val[i] 
            count += mod_val_dict[need_val_i]
            print(count)
from collections import Counter

class Solution:
    def subarraysDivByK(self, A, K: int) -> int:
        mod_val = []
        for a in A:
            if not mod_val:
                mod_val.append(a % K)
            else:
                val = (a % K + mod_val[-1]) % K
                mod_val.append(val)
        mod_val_dict = Counter(mod_val)
        print(mod_val_dict, mod_val)
        
        N = len(A)
        count = 0
        for i in range(N):
            val_a = A[i]
            if val_a % K == 0:
                count += 1
            for j in range(i+1, N):
                if i - 1 > -1:
                    print(A[i], A[j])
                    need_mod = mod_val[j] - mod_val[i-1]
                    if need_mod in mod_val_dict:
                        count += mod_val_dict[need_mod]
        return count
# 暴力解法
class Solution:
    def subarraysDivByK(self, A, K: int) -> int:
        count, N = 0, len(A)
        for i in range(N):
            for j in range(i, N):
                sub_arr_sum = sum(A[i:j+1])
                print(sub_arr_sum)
                if sub_arr_sum % K == 0:
                    count += 1
        return count
solution = Solution()
solution.subarraysDivByK(A = [4,5,0,-2,-3,1], K = 5)
# 暴力解法 -- 前缀和
class Solution:
    def subarraysDivByK(self, A, K: int) -> int:
        count, N = 0, len(A)
        prefix_sum = []
        for a in A:
            if not prefix_sum:
                prefix_sum.append(a)
            else:
                prefix_sum.append(a + prefix_sum[-1])
        print(prefix_sum)
        prefix_sum = [0] + prefix_sum
        A = [0] + A
        for i in range(1, N+1):
            for j in range(i, N+1):
                sub_sum = prefix_sum[j] - prefix_sum[i-1]
                if sub_sum % K == 0:
                    count += 1
        return count
# 前缀和 +
class Solution:
    def subarraysDivByK(self, A, K: int) -> int:
        count, N = 0, len(A)
        prefix_sum = []
        for a in A:
            if not prefix_sum:
                prefix_sum.append(a)
            else:
                prefix_sum.append(a + prefix_sum[-1])
                
        print(prefix_sum)
        prefix_sum = [0] + prefix_sum
        A = [0] + A
        for i in range(1, N+1):
            for j in range(i, N+1):
                # 如果 prefix_sum[j] - prefix_sum[i-1] = sub_arr_sum可以整出K的话，说明 prefix_sum[j] 和 prefix_sum[i]对k的模是相同的
                sub_sum = prefix_sum[j] - prefix_sum[i-1]
                if sub_sum % K == 0:
                    count += 1
        return count
from collections import Counter, defaultdict

class Solution:
    def subarraysDivByK(self, A, K: int) -> int:
        count, N = 0, len(A)
        seen = defaultdict(int)
        seen[0] = 1
        runner = 0
        for i, val in enumerate(A):
            runner = (runner + val) % K # 当前值对k的余数
            count += seen[runner]
            seen[runner] += 1
        return count
solution = Solution()
solution.subarraysDivByK(A = [4,5,0,-2,-3,1], K = 5)<jupyter_output>4 0 defaultdict(<class 'int'>, {0: 1, 4: 1})
4 1 defaultdict(<class 'int'>, {0: 1, 4: 2})
4 3 defaultdict(<class 'int'>, {0: 1, 4: 3})
2 3 defaultdict(<class 'int'>, {0: 1, 4: 3, 2: 1})
4 6 defaultdict(<class 'int'>, {0: 1, 4: 4, 2: 1})
0 7 defaultdict(<class 'int'>, {0: 2, 4: 4, 2: 1})
{'fraction_non_alphanumeric': 0.13309608540925266, 'fraction_numerical': 0.03558718861209965, 'mean_word_length': 1.491725768321513, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '364015', 'license': 'Apache-2.0', 'n_tokens_mistral': 1665, 'n_tokens_neox': 1554, 'n_words': 412, 'path': 'Hash Table/1018/974. Subarray Sums Divisible by K.ipynb', 'repo_name': 'YuHe0108/Leetcode', 'size': '4215'}