湖北省建设信息网站,瓷器网站源码,网页开发设计公司,深圳福田做网站公司560 和为k的子数组
给你一个整数数组 nums 和一个整数 k #xff0c;请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。 思路#xff1a;一次遍历元素#xff0c;当当前累积和超过k时#xff08;若当前元素k#xff0c;直接切换…560 和为k的子数组
给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。 思路一次遍历元素当当前累积和超过k时若当前元素k直接切换到下一元素去除前置元素至和小于k用长度length调用前置元素 class Solution(object):def subarraySum(self, nums, k)::type nums: List[int]:type k: int:rtype: intsumm, length, out 0, 0, 0for i, val in enumerate(nums):if val k:summ, length 0, 0out 1 if val k else 0continueelse:summ, length summval, length1if summ k:continueelse:while summ k: length - 1summ - nums[i-length] if summ k:length - 1summ - nums[i-length]out1return out#这一版代码只适用于数组元素为正的情况...只能通过32/93个案例 官方思路前缀和 sum[i, j] pre[j]-pre[i-1]k 由于 i-1j所以遍历到下标 j 时就能判断 [0,j] 内有多少满足求和条件的子数组 class Solution(object):def subarraySum(self, nums, k)::type nums: List[int]:type k: int:rtype: inttmp {0:1}summ, out 0, 0for i in range(len(nums)):summ nums[i]out tmp[summ-k] if summ-k in tmp else 0 tmp[summ] 1 if summ not in tmp else tmp[summ]1#在[0:i-1]内搜索前缀和再更新[0;j]的前缀和 return out 239 滑动窗口最大值
给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。 官方思路当窗口右滑 有新元素入窗时移出所有值小于新元素的元素再判断现有最大值是否超出窗口长度 用双向队列来维护当前窗口内元素坐标 from collections import dequeclass Solution(object):def maxSlidingWindow(self, nums, k)::type nums: List[int]:type k: int:rtype: List[int]idx deque()out []for i in range(len(nums)):while idx and nums[i] nums[idx[-1]]: #pop对空队列操作会报错idx.pop()idx.append(i)# if i k-1:out.append(nums[idx[0]]) #ik-1时刚好取完第一个窗口长度此时需要取一次最大值if i k-1: while idx[0] i-k: #当ik时才会需要判断最大值是否超过窗口idx.popleft()out.append(nums[idx[0]])return out 双端队列
1.len(deque)
2.deque.appendleft(val) #将val插入到队头deque.append(val) #将val插入到队尾deque.insert(idx, val) #将val放在idxidx越界时会自动更改到边界位置deque.extendleft(list) #将list插入到队头 会改变list中元素的相对位置deque.extend(list) #将list插入到队尾
3.deque.popleft() #移除队头元素deque.pop() #移除队尾元素队列为空会报错
4.deque[idx] val #通过索引更改元素
5.deque.index(val) #查找元素对应的索引没有匹配会报错
6.deque.count(val) #统计val的数量
7.deque.remove(val) #移除第一个匹配的元素没有匹配会报错deque.clear() #清空
8.deque.reverse() #翻转deque.rotate(k) #循环右移k步首尾相接
76 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 官方思路用双指针维护一个滑动窗口先增大right指标至窗口内能找到t中的全部字母然后移动left指标缩小窗口在即将要破坏满足全部字母的条件时若此时窗口长度更小则记录下指针坐标 class Solution(object):def minWindow(self, s, t)::type s: str:type t: str:rtype: strif len(s) len(t):return hasht {}left, right, out 0, 0, [0, len(s)1]for i in range(len(t)): #用counter可以直接生成字典hasht[t[i]] hasht[t[i]] 1 if t[i] in hasht else 1while right len(s):if s[right] in hasht: hasht[s[right]] hasht[s[right]] - 1 while max(hasht.values()) 0 and left right: #此时找到所有元素移动left指针if s[left] in hasht: hasht[s[left]] hasht[s[left]] 1if right-leftout[1]-out[0]:out[0], out[1] left, right1 #切片右侧取不到left 1right 1return if out[1]len(s) else s[out[0]:out[1]] 优化max(hasht.values()) 0 需要每次遍历可以用needcnt记录欠缺元素的数量 class Solution(object):def minWindow(self, s, t)::type s: str:type t: str:rtype: strif len(s) len(t):return left, right, out 0, 0, [0, len(s)1]needcnt len(t)hasht Counter(t)while right len(s):if s[right] in hasht: hasht[s[right]] hasht[s[right]] - 1 if hasht[s[right]] 0: needcnt - 1 #只有hasht[s[i]]为负时才是重复元素 while needcnt 0 and left right: if s[left] in hasht: hasht[s[left]] hasht[s[left]] 1if hasht[s[left]] 0: needcnt 1 #只有hasht[s[i]]为正时才是欠缺元素if right-leftout[1]-out[0]:out[0], out[1] left, right1 left 1right 1return if out[1]len(s) else s[out[0]:out[1]]
