文章目录
- 使用前缀和+哈希表
- 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 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