深圳住房和城乡建设部网站,中国核工业第五建设有限公司海南,东莞市企慕网络科技有限公司,如何设计一个网页首页代码文章目录 使用前缀和哈希表560.和为K的子数组525.连续数组2588.统计美丽子数组数目 子数组的定义是原来的数组当中连续的非空的序列#xff0c;而我们的背包问题的选与不选的情况#xff0c;对应的是这个非连续的情况,那么这种情况就要注意当然啦#xff0c;对于线性的时间内… 文章目录 使用前缀和哈希表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]*(n1)for i in range(n):pre[i1] pre[i] nums[i]# pre[i] - pre[j] k ,那么只需在哈希表中查询这个pre[i] - k 的个数即可ans 0# 注意这个 0:1也要加进去for i in range(n1):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]*(n1)for i in range(n):pre[i1] pre[i] newnum[i]store {}ans 0for i in range(n1):# 判断该键是否出现过if pre[i] in store.keys():ans max(ans,i - store[pre[i]])else:store[pre[i]] ireturn ans2588.统计美丽子数组数目
2588.统计美丽子数组数目 子数组是全部为0也就是和值为0那么对于减去的每一位来说其实就是要求对应位数上的1是偶数个数的对于判断是否是偶数个1那么我们直接考虑使用这个 异或进行操作也就是 异或值为0的子数组的个数情况
from collections import defaultdict
class Solution:def beautifulSubarrays(self, nums: List[int]) - int:# 求解方案数n len(nums)# 异或前缀pre [0]*(n1)for i in range(n):pre[i1] pre[i]^nums[i]store defaultdict(int)# 遍历ans 0for i in range(n1):ans store[pre[i]]store[pre[i]] 1return ans
