- 区间和的数量统计是一类十分典型的问题：
记录左边，枚举右边策略 - 前置题目：
统计nums[j]==nums[i]的对数 - 进阶版本：
统计子数组和%modulo == k的子数组的数目 - 为什么要使用到这个
哈希表？ - 答：对于有限状态的数量的存储，并且对于
数量的统计，需要初始化store[0]=1,当然对于长度的统计，那么初始化的情况就是store[0] = -1(存储的是下标) - 为什么要使用到这个
前缀和？ - 答：方便计算这个区间的和的情况，我们所使用的前缀和，就是通过两个前缀的状态的差求解出中间状态的情况！！！！
1512.好数对的数目
- 典型的
哈希表问题,先更新答案，再更新哈希表
from collections import defaultdict
class Solution:
def numIdenticalPairs(self, nums: List[int]) -> int:
n = len(nums)
store = defaultdict(int)
ans = 0
for i in range(n):
ans += store[nums[i]]
store[nums[i]] += 1
return ans
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] = 1
else:
nums[i] = 0
# 哈希表存储，k == 0 的情况得另外处理，当k!=0的时候，就是一个哈希表+前缀和的问题
store = defaultdict(int)
# 记录的是对应的取模的结果的最早的下标
# 区间和取模问题
store[0] = 1
tmp,ans = 0,0
for i in range(n):
tmp = tmp + nums[i]
if tmp >= k:
ans += store[(tmp - k) % modulo]
store[tmp % modulo ] += 1
return ans
思考
- 如果题目求解的是
子数组的和是modulo的倍数的子数组个数，应该如何求解？ - 答：那其实就更加简单了，我们只需记录
nums[i]%modulo的结果在左边的数量即可，不过要注意初始化的时候得store[0] = 1
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 = 0
for 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] = i
return ans