算法 之 前缀和 与 滑动窗口 与 背包问题 的差异(子数组之和为k问题)

• 子数组的定义是原来的数组当中连续的非空的序列，而我们的背包问题的选与不选的情况，对应的是这个非连续的情况,那么这种情况就要注意
• 当然啦，对于线性的时间内解决的问题我们可能会想到使用滑动窗口进行处理的问题，但是应该要注意 滑动窗口只适合用于单调的情况，也就是说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 ans

525.连续数组

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