Python C++ prefix sum mod k陣列和公式解Leetcode 974 Subarray Sums Divisible...

Python C++ prefix  sum  mod k陣列和公式解Leetcode 974  Subarray Sums Divisible by K

昨天的問題523. Continuous Subarray Sum會解，今日Leetcode 974. Subarray Sums Divisible by K更沒問題，看一下constraints hash map就不用了，馬上就能解答

Python code請進

----------

Yesterday's question 523. Continuous Subarray Sum can be solved. Today's Leetcode 974. Subarray Sums Divisible by K is no problem. Take a look at the constraints and you can solve it immediately without hash map.

[codes on Leetcode]https://leetcode.com/problems/subarray-sums-divisible-by-k/solutions/5281688/array-for-prefix-sum-mod-k-sum-vs-recursion-11ms-beats-99-95/

[Python C++使用prefix sum mod k + hash map解Leetcode523 Continuous Subarray Sum]https://www.youtube.com/watch?v=QSO7-Vh87Os

[Prefix sum play list]https://www.youtube.com/watch?v=1kA_aZHewmU&list=PLYRlUBnWnd5LkYN-5ptHDrtPXOuHm9uSq

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        mod_k=[0]*k
        mod_k[0]=1
        prefix=0
        for x in nums:
            prefix=(prefix+x)%k
            if prefix<0: prefix+=k
            mod_k[prefix]+=1
        ans=0
        for n in mod_k:
            ans+=n*(n-1)//2
        return ans