区间和数量统计 之 前缀和+哈希表

• 区间和的数量统计是一类十分典型的问题：记录左边，枚举右边策略
• 前置题目：统计nums[j]==nums[i]的对数
• 进阶版本：统计子数组和%modulo == k的子数组的数目
• 为什么要使用到这个哈希表？
• 答：对于有限状态的数量的存储，并且对于数量的统计，需要初始化store[0]=1,当然对于长度的统计，那么初始化的情况就是store[0] = -1(存储的是下标)
• 为什么要使用到这个前缀和？
• 答：方便计算这个区间的和的情况，我们所使用的前缀和，就是通过两个前缀的状态的差求解出中间状态的情况！！！！

1512.好数对的数目

1512.好数对的数目

• 典型的哈希表问题,先更新答案，再更新哈希表

from collections import defaultdict
class Solution:def numIdenticalPairs(self, nums: List[int]) -> int:n = len(nums)store = defaultdict(int)ans = 0for i in range(n):ans += store[nums[i]]store[nums[i]] += 1return ans

2845.统计趣味子数组的数目

2845.统计趣味子数组的数目

• 子数组区间和取模的问题，还是采用记录左边，枚举右边策略
• 不过就是要注意，我们其实是只用枚举(前缀和-k)%modulo的数是否在左边出现，更新的时候是前缀和%modulo的数量+1

from collections import defaultdict
class Solution:def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:n = len(nums)# 预处理，将满足的位置变为1，否则就是0 for i in range(n):if nums[i] % modulo == k:nums[i] = 1else:nums[i] = 0 # 哈希表存储，k == 0 的情况得另外处理，当k!=0的时候，就是一个哈希表+前缀和的问题store = defaultdict(int)# 记录的是对应的取模的结果的最早的下标# 区间和取模问题store[0] = 1tmp,ans = 0,0for i in range(n):tmp = tmp + nums[i]if tmp >= k:ans += store[(tmp - k) % modulo]store[tmp  % modulo ] += 1return ans

思考

• 如果题目求解的是子数组的和是modulo的倍数的子数组个数，应该如何求解？
• 答：那其实就更加简单了，我们只需记录nums[i]%modulo的结果在左边的数量即可，不过要注意初始化的时候得store[0] = 1

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

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

• 哈希表存储的是下标，所以初始化的时候注意得是store[0]=-1
• 我们只需关注这个字符串中元音的个数的情况，当然，由于两个前缀相同的状态的差的字符串中元音的个数肯定是偶数,所以我们采用前缀和来求解出字符串中元音的个数的状态，由于涉及到奇数偶数，所以采用异或运算

class Solution:def findTheLongestSubstring(self, s: str) -> int:n = len(s)mapper = {"a" : 1,"e" : 2,"i" : 4,"o" : 8,"u" : 16}# 使用哈希表存储异或结果出现的第一次的下标seen = {0:-1}# 记录结果ans = cur = 0for i in range(n):if s[i] in mapper:cur ^= mapper[s[i]]# 判断当前的cur是否是第一次出现if cur in seen:ans = max(ans,i-seen[cur])else:seen[cur] = ireturn ans