前缀和汇总_牛客博客

leet560 求和等于 K 的子数组数量

（1）暴力解法

（2）前缀和

sum(i~j) = s(j) - s(i-1) = k

s(j) - k = s(i-1)

保存三个状态： sum,sum-k,cnt

def subarraySum(self, nums: List[int], k: int) -> int:
        if not nums or len(nums) == 0:
            return 0
        mapping = {0:1}
        sum,cnt = 0,0
        for num in nums:
            sum += num
            if sum-k in mapping:
                cnt+= mapping[sum-k]
            if sum not in mapping:
                mapping[sum] = 1
            else:
                mapping[sum] +=1
        return cnt

1248. 统计「优美子数组」

给你一个整数数组 nums 和一个整数 k。
如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
请返回这个数组中「优美子数组」的数目。

用一个表保存：i个奇数的情况出现了几次；初始0个奇数的情况出现了1次；

再用一个变量count保存到当前位置为止一共出现了几个奇数，如果count-k在表里，那么说明前面有mapping[count-k]个子串里面有k个奇数。

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        from collections import defaultdict
        mapping =defaultdict(int) #mapping保存i个奇数的情况出现了多少次
        mapping[0] = 1   
        resEven,countEven = 0,0 # resEven保存最后的结果， countEven保存到当前位置为止，一共出现了多少个奇数

        for i in range(len(nums)):
            if nums[i] % 2==1:
                countEven+=1
            mapping[countEven]+=1

            if countEven-k in mapping.keys():
                resEven+= mapping[countEven-k]

        return resEven

1371. 每个元音包含偶数次的最长子字符串

给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次。

参考：https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/solution/xiang-xi-jie-shi-by-will_never_die/

对每一个元音字母维护一个前缀和pre[i][k],表示前i个字符中，第k个元音字母一共出现的次数。

因为要出现偶数次，因此两个前缀和pre[i][k]和pre[j][k]的奇偶性一定是相同的

aeiou对应 00001,00010,00100,01000,10000(0表示出现了偶数次，1表示出现了奇数次)

dp[pattern] 表示当前索引值下对应的元音奇偶次数组合特征

异或时，如果出现偶数次，对应位为0，否则为1；

所以再次出现pattern时，一定满足题意。

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        dp = [-float('inf')]*32
        dp[0] = -1
        pattern = 0
        res = 0
        for i in range(len(s)):
            if s[i] == 'a':
                pattern^= (1<<0)
            elif s[i] == 'e':
                pattern^= (1<<1)
            elif s[i] == 'i':
                pattern^= (1<<2)
            elif s[i] == 'o':
                pattern^= (1<<3)
            elif s[i] =='u':
                pattern ^= (1<<4)
            if dp[pattern] != -float('inf'):
                cur_len=i-dp[pattern]
                res=max(res,cur_len)
            else:
                dp[pattern] =i
        return res

974. 和可被 K 整除的子数组

参考：https://leetcode-cn.com/problems/subarray-sums-divisible-by-k/solution/xiong-mao-shua-ti-python3-you-qian-zhui-he-fu-xi-p/

给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。

dict中只存储前缀和对 K 的模出现的次数

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        res = 0
        pre_mod = 0  # 存储当前位置的上一个位置的前缀和的余数加上当前位置的值对K的余数
        presum_count = collections.defaultdict(int)
        presum_count[0] = 1
        for i in range(len(A)):
            pre_mod = (pre_mod + A[i]) % K
            # 下面这行感觉最不好理解
            res += presum_count[pre_mod]  # 如果能在dict中找到相同的pre_mod，说明当前节点前的某个位置的前缀和到当前位置的前缀和间存在若干个K
            presum_count[pre_mod] += 1
        return res