526互联

前缀和 与 区间

发布时间 2023-09-11 22:51:30作者: 深渊之巅

思想 a ~ b区间可以转换为 0 ~ b - 0 ~ (a - 1)

用这种前缀和的思想，可以快速枚举所有合格条件的自区间。

 

 

 

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        m = dict()
        m[0] = 1
        cur, res = 0, 0
        for num in nums:
            cur += num
            if cur - k in m:
                res += m[cur - k]
            if cur in m:
                m[cur] += 1
            else:
                m[cur] = 1

        return res

 

 

 

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        m = dict()
        m[0] = 1

        cur, res = 0, 0
        for num in nums:
            cur = (cur + num) % k
            if cur in m:
                res += m[cur]
            if cur in m:
                m[cur] += 1
            else:
                m[cur] = 1
        
        return res

 

 

 

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            if nums[i] == 0:
                nums[i] = -1

        cur, res = 0, 0

        mp = dict()
        mp[0] = -1

        for i, num in enumerate(nums):
            cur += num
            if cur in mp:
                res = max(res, i - mp[cur])
            else:
                mp[cur] = i

        return res