herrDeng網內搜尋

自訂搜尋

Ads

2024年6月9日 星期日

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

        
 

沒有留言:

Related Posts Plugin for WordPress, Blogger...

熱門文章