Leetcode刷题-不定长滑动窗口
分享丨【题单】滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环） - 力扣（LeetCode）
3090
class Solution:
def maximumLengthSubstring(self, s: str) -> int:
c = Counter()
res = 0
rk = -1
for i in range(len(s)):
if i != 0:
# 左指针向右移动一格，移除一个字符
c[s[i - 1]] -= 1
while rk + 1 < len(s) and c[s[rk + 1]] < 2 :
# 不断地移动右指针
c[s[rk + 1]] += 1
rk += 1
res = max(res, rk - i + 1)
return res
1493
思路：使用一个变长的滑动窗口进行扫描，当窗口中元素的状态符合题目要求时，窗口继续扩大，答案即为最大的窗口值减去删去的元素的数目。
class Solution:
def longestSubarray(self, nums: List[int]) -> int:
d = 0 #删除的元素的数目
left = 0 #窗口的左端
res = 0 #窗口的右端
#从最左端开始，将每个元素添加到窗口中
for i in range(len(nums)):
#如果该元素为0，则删除
if nums[i] == 0:
d += 1
#移动左端点直到删除元素的数目小于2为止
while left < len(nums) and d == 2:
if nums[left] == 0:
d -= 1
left += 1
#记录最大的窗口值
res = max(res, i - left + 1 - d)
#如果最大窗口值和数组长度相同，说明数组中没有0元素，又因必须删除一个元素，所以返回res-1
if res == len(nums):
return res - 1
return res1208
思路：使用变长滑动窗口，与1493差别不大。
class Solution:
def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
changeCost = 0
left = 0
res = 0
for i in range(len(s)):
changeCost += math.fabs(ord(s[i]) - ord(t[i]))
while changeCost > maxCost and left < len(s):
changeCost -= math.fabs(ord(s[left]) - ord(t[left]))
left += 1
res = max(res, i - left + 1)
return res
2730
思路：与1493、1208相似，变长滑动窗口的不同运用。
class Solution:
def longestSemiRepetitiveSubstring(self, s: str) -> int:
res = 0
left = 0
p = 0
if len(s) == 1:
return 1
for i in range(1,len(s)):
if s[i] == s[i - 1]:
p += 1
while p > 1 and left < len(s) - 1:
if s[left] == s[left + 1]:
p -= 1
left += 1
res = max(res, i - left + 1)
return res904
思路：使用一个哈希表存储每次摘的水果，当采摘的水果种类大于2时，窗口的左端点向右一直移动，知道采摘的水果种类不超过2为止，然后记录每次移动左端或者右端后窗口的值，最大值即为答案。
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
s = Counter()
left = 0
res = 0
for i in range(len(fruits)):
s[fruits[i]] += 1
while len(s) > 2:
#去掉最左端这个水果
s[fruits[left]] -= 1
#如果这个种类的水果数量为0了，就从篮子里删掉这一个种类
if s[fruits[left]] == 0:
del s[fruits[left]]
left += 1
res = max(res, i - left + 1)
return res1695
class Solution:
def maximumUniqueSubarray(self, nums: List[int]) -> int:
res = 0
now = 0
left = 0
c = Counter()
for i in range(len(nums)):
c[nums[i]] += 1
now += nums[i]
while c[nums[i]] > 1 and left < i:
c[nums[left]] -= 1
now -= nums[left]
left += 1
res = max(res, now)
return res2958
class Solution:
def maxSubarrayLength(self, nums: List[int], k: int) -> int:
res = 0
left = 0
c = Counter()
for i in range(len(nums)):
c[nums[i]] += 1
while c[nums[i]] > k and left < i:
c[nums[left]] -= 1
left += 1
res = max(res, i - left + 1)
return res
2779
class Solution:
def maximumBeauty(self, nums: List[int], k: int) -> int:
nums.sort()
res = 0
left = 0
for i in range(len(nums)):
while nums[i] - nums[left] > 2*k:
left += 1
res = max(res, i - left + 1)
return res
2024
class Solution:
def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
c = Counter()
left = 0
res = 0
for i in range(len(answerKey)):
c[answerKey[i]] += 1
while min(c["T"], c["F"]) > k:
c[answerKey[left]] -= 1
left += 1
res = max(res, i - left + 1)
return res
1004
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
res = 0
left = 0
z = 0
for i in range(len(nums)):
if nums[i] == 0:
z += 1
while z > k:
if nums[left] == 0:
z -= 1
left += 1
res = max(res, i - left + 1)
return res1658
class Solution:
def minOperations(self, nums: List[int], x: int) -> int:
left = 0
res = -1
s = sum(nums) - x
for i in range(len(nums)):
s -= nums[i]
while s < 0 and left <= i:
s += nums[left]
left += 1
if s == 0:
res = max(res, i - left + 1)
if res >= 0:
return len(nums) - res
else:
return -1
1838
思路：使用变长滑动窗口，先对数组进行排序，每次加入元素时将所有在窗口内的元素递增到最大那个数（也就是当前加入的数），由于前面有i - left个元素已经递增到第 i 个数，所以此时需要递增(nums[i] - nums[i - 1]) * (i - left)次，当递增次数大于k时，持续移动左端点直到小于k为止。
class Solution:
def maxFrequency(self, nums: List[int], k: int) -> int:
if len(nums) == 1:
return 1
nums.sort()
left = 0
res = 0
now = 0
for i in range(1,len(nums)):
now += (nums[i] - nums[i - 1]) * (i - left)
while now > k:
now -= (nums[i] -nums[left])
left += 1
res = max(res, i - left + 1)
return res
2516
class Solution:
def takeCharacters(self, s: str, k: int) -> int:
c = Counter()
n = len(s)
for i in range(len(s)):
c[s[i]] += 1
print(c)
if c['a'] < k or c['b'] < k or c['c'] < k:
return -1
res = 0
left = -1
for i in range(len(s)):
c[s[i]] -= 1
while c[s[i]] < k:
left += 1
c[s[left]] += 1
res = max(res, i - left + 1)
return n - res + 12831
class Solution:
def longestEqualSubarray(self, nums: List[int], k: int) -> int:
pos_lists = defaultdict(list)
for i, x in enumerate(nums):
pos_lists[x].append(i - len(pos_lists[x]))
ans = 0
for pos in pos_lists.values():
if len(pos) <= ans:
continue # 无法让 ans 变得更大
left = 0
for right, p in enumerate(pos):
while p - pos[left] > k: # 要删除的数太多了
left += 1
ans = max(ans, right - left + 1)
return ans