3数组-滑动窗口-长度最小的子数组/ 水果成篮/最小覆盖子串/替换后的最长重复字符

本文主要是介绍3数组-滑动窗口-长度最小的子数组/ 水果成篮/最小覆盖子串/替换后的最长重复字符，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3] 输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：

输入：target = 4, nums = [1,4,4] 输出：1
示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:sum=0n=len(nums)res=n+1j=0#i是右指针 j左指针for i in range(0,n):sum+=nums[i]# 如果sum持续大于target 就不右移扩大窗口 而是左移缩小窗口while(sum>=target):# 因为满足sum>=target 所以更新当前区间长度res=min(res,i-j+1)sum-=nums[j]j+=1#跳出循环 说明sum不满足>=target 所以需要继续移动右指针# 如果res没有被赋值 则返回0if res==n+1:return 0else:return res

904. 水果成篮

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

你只有两个篮子，并且每个篮子只能装单一类型的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从每棵树（包括开始采摘的树）上恰好摘一个水果。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的最大数目。

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。
示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。
示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fruit-into-baskets
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：freq数组记录现在窗口中两种水果的数目，count记录现在窗口中有多少种不同的水果，如果count<=2，那么right指针可以一直向右移动，直到count>2,当count>2时，说明窗口中的水果种类超过2，为了减少水果种类，left指针就要向右移动，移动的同时还要更新freq数组，最后取最大值即可。

模板

def findSubArray(nums):N = len(nums) # 数组/字符串长度left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间sums = 0 # 用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数res = 0 # 保存最大的满足题目要求的 子数组/子串 长度while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾sums += nums[right] # 增加当前右边指针的数字/字符的求和/计数while 区间[left, right]不符合题意：# 此时需要一直移动左指针，直至找到一个符合题意的区间sums -= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反# 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串res = max(res, right - left + 1) # 需要更新结果right += 1 # 移动右指针，去探索新的区间return res作者：fuxuemingzhu
链接：https://leetcode-cn.com/problems/max-consecutive-ones-iii/solution/fen-xiang-hua-dong-chuang-kou-mo-ban-mia-f76z/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution:def totalFruit(self, fruits: List[int]) -> int:# 本质上是 最多包含两个不同字符的最长连续字串left=0n=len(fruits)# freq 计算每种类出现的频次 count计算品种数量# freq 相当于hash表 长度要是len和max(fruit)的最大值 防止出现[1,2,3,3,46]这种freq=[0]*max(max(fruits),n)count=0res=0for right in range(0,n):freq[fruits[right]]+=1#说明第一次加入该品种 种类加1if freq[fruits[right]]==1:count += 1# 品种种类大于2 移动左指针 缩小窗口while(count>2):#一直减少左指针指向的品种 直到该品种数量为0 则种类减1freq[fruits[left]]-=1if freq[fruits[left]]==0:count-=1left+=1#更新区间res=max(res,right-left+1)return res

1004. 最大连续1的个数 III

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回数组中连续 1 的最大个数。

示例 1：

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2 输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 6。示例 2：

输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 10。

class Solution(object):def longestOnes(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""# 本质是确保窗口内0的个数小于等于k个left,right=0,0res=0# 分别计算0,1的个数count=[0,0]n=len(nums)while(right<n):count[nums[right]]+=1# 如果0的个数大于k 则移动左窗口到保持在窗口内0的个数为k的程度while(count[0]>k):count[nums[left]]-=1left+=1#跳出循环 说明此时窗口内0的数量等于k 更新窗口res=max(res,right-left+1)right+=1return res

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = “ADOBECODEBANC”, t = “ABC” 输出：“BANC”
示例 2：

输入：s = “a”, t = “a” 输出：“a”
示例 3:

输入: s = “a”, t = “aa” 输出: “” 解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

class Solution:def minWindow(self, s: str, t: str) -> str:need = collections.defaultdict(int)for c in t:need[c] += 1needCnt = len(t)i = 0 #记录起始位置res = (0, float('inf'))  #用两个元素，方便之后记录起终点#三步骤：#1. 增加右边界使滑窗包含tfor j,c in enumerate(s):# 大于0说明是串t需要的元素，且s中也有，随着右滑，所以【真正】需要的元素个数--if need[c] >0:needCnt -= 1#随着右滑，【所有】需要的元素--need[c] -= 1 #这行放在外面不可以，看19行 need[c] == 0#2. 收缩左边界直到无法再去掉元素   !注意，处理的是i#needCnt == 0 说明已经右滑到了包含t的所有元素if needCnt == 0:while True:c = s[i]if need[c] == 0: #表示再去掉就不行了(need>0)breakelse:need[c] += 1i += 1# 跳出了循环，更新结果if j-i < res[1] - res[0]:  #这里是否减一都可以，只要每次都是这样算的就行，反正最后也是输出子串而非长度res = (i,j)#3. i多增加一个位置，准备开始下一次循环(注意这步是在 needCnt == 0里面进行的 )# 此时need[s[i]]=need[c]==0 所以是满足条件的，所以要准备下一次移动了，所以现在要去掉need[s[i]]，然后继续右滑need[s[i]] += 1needCnt += 1    #由于 移动前i这个位置 一定是所需的字母，因此NeedCnt才需要+1i += 1return "" if res[1]>len(s) else s[res[0]: res[1]+1]

题解参考：https://leetcode-cn.com/problems/minimum-window-substring/solution/tong-su-qie-xiang-xi-de-miao-shu-hua-dong-chuang-k/

424. 替换后的最长重复字符

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。

在执行上述操作后，返回包含相同字母的最长子字符串的长度。

示例 1：

输入：s = “ABAB”, k = 2 输出：4 解释：用两个’A’替换为两个’B’,反之亦然。
示例 2：

输入：s = “AABABBA”, k = 1 输出：4 解释：
将中间的一个’A’替换为’B’,字符串变为 “AABBBBA”。
子串 “BBBB” 有最长重复字母, 答案为 4。

class Solution(object):def characterReplacement(self, s, k):""":type s: str:type k: int:rtype: int"""# 本质上是这个窗口内出现次数最多的那个字符之外  的其余字符之和不大于kcount = collections.Counter()left = 0res = 0nums = list(s)for right, x in enumerate(nums):count[x] += 1# 当前区间长度-出现次数最多的那个字符的次数=其他字符 >k 则移动左指针while ((right - left + 1)-max(count.values()) > k):count[nums[left]] -= 1# if (count[nums[left]] == 0):#     del count[nums[left]]left+=1res = max(res, right - left + 1)return res'''"ABABCCC"2'''

3最长无重复子串

https://leetcode.cn/problems/longest-substring-without-repeating-characters/solution/hua-dong-chuang-kou-by-nifty-snyder0f5-0auy/

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:left,right = 0,0res = 0if len(s) == 0:return 0if s.count(s[0]) == len(s):return 1if len(set(s)) == len(s):return len(s)while right < len(s):if s[right] not in s[left:right]:right +=1res = max(res,len(s[left:right]))else:while s[right] in s[left:right]:left +=1return res作者：nifty-snyder0f5
链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/solution/hua-dong-chuang-kou-by-nifty-snyder0f5-0auy/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。``````python
class Solution:def lengthOfLongestSubstring(self, s: str) -> int:n = len(s)left,right = 0,0res = 0 # 子串长度while right<n:# 不满足区间的要求 左指针移动while s[right] in s[left:right]:left +=1 # 左指针右移# 满足区间长度 更新res和右指针移动res = max(res,right-left+1)right+=1return res