文章目录
- 使用前缀和+哈希表
- 560.和为K的子数组
- 525.连续数组
- 2588.统计美丽子数组数目
- 子数组的定义是原来的数组当中
连续的非空的序列，而我们的背包问题的选与不选的情况，对应的是这个非连续的情况,那么这种情况就要注意 - 当然啦，对于线性的时间内解决的问题
我们可能会想到使用滑动窗口进行处理的问题，但是应该要注意滑动窗口只适合用于单调的情况，也就是说nums数组是全部为非负数或者非正数的情况- 我们所使用能够使用滑动窗口求解这个子数组的和为
k的情况，基于的理念就是，控制滑动窗口的l和r，当<k的时候，窗口向右边扩大，>k的情况，就窗口左边缩小，这个理论必须是基于单调的，也就是窗口越大，这个窗口的和值就越大
- 我们所使用能够使用滑动窗口求解这个子数组的和为
- 对于前缀和来说，适用的场景就没有那么多的限制，任意的子数组之和都可以转化为前缀和的差
前缀和与查分的补充
- 这个前缀和与哈希表的组合，有求解方案数(
和为k值的方案数)，那么记录的是每种和值所出现的次数，对于长度问题来说，就是统计每种和值所出现的最小的下标
使用前缀和+哈希表
560.和为K的子数组
560.和为K的子数组
思路分析
- 首先求解的是连续的情况，所以考虑使用滑动窗口以及这个前缀和，但是由于存在正数和负数同时存在，所以就只能使用这个
前缀和+哈希表
from collections import defaultdict
class Solution:def subarraySum(self, nums: List[int], k: int) -> int:# 不单调，不能使用这个滑动窗口# 使用前缀和，但是为了不用两层循环进行遍历，所以我们得使用一个哈希表进行处理n = len(nums)store = defaultdict(int)pre = [0]*(n+1)for i in range(n):pre[i+1] = pre[i] + nums[i]# pre[i] - pre[j] = k ,那么只需在哈希表中查询这个pre[i] - k 的个数即可ans = 0# 注意这个 0:1也要加进去for i in range(n+1):ans += store[pre[i] - k]store[pre[i]] += 1return ans525.连续数组
525.连续数组
- 参照
和为k的子数组的思路，但是你会发现一个问题，这个0,1的统计时分难统计，难道要直接分别统计0和1各自的数量吗？ - 当然不是，所以得进行巧妙的转换：把这个
0替换成-1,然后我们只需统计这个和为0最长子数组即可，在使用哈希表的时候，我们不是记录这个某个和值的出现的次数，而是改为记录该和值出现的最小的下标
class Solution:def findMaxLength(self, nums: List[int]) -> int:n = len(nums)newnum = [0]*n # 进行转化for i in range(n):if nums[i] == 0:newnum[i] = -1else:newnum[i] = 1# 求解前缀和pre = [0]*(n+1)for i in range(n):pre[i+1] = pre[i] + newnum[i]store = {}ans = 0for i in range(n+1):# 判断该键是否出现过if pre[i] in store.keys():ans = max(ans,i - store[pre[i]])else:store[pre[i]] = ireturn ans
2588.统计美丽子数组数目
2588.统计美丽子数组数目
- 子数组是全部为0，也就是和值为0，那么对于减去的每一位来说，其实就是要求对应位数上的
1是偶数个数的，对于判断是否是偶数个1，那么我们直接考虑使用这个异或进行操作，也就是异或值为0的子数组的个数情况
from collections import defaultdict
class Solution:def beautifulSubarrays(self, nums: List[int]) -> int:# 求解方案数n = len(nums)# 异或前缀pre = [0]*(n+1)for i in range(n):pre[i+1] = pre[i]^nums[i]store = defaultdict(int)# 遍历ans = 0for i in range(n+1):ans += store[pre[i]]store[pre[i]] += 1return ans
