分享丨【题单】滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环） - 力扣（LeetCode）

3090

class Solution:def maximumLengthSubstring(self, s: str) -> int:c = Counter()res = 0rk = -1for i in range(len(s)):if i != 0:# 左指针向右移动一格，移除一个字符c[s[i - 1]] -= 1while rk + 1 < len(s) and c[s[rk + 1]] < 2 :# 不断地移动右指针c[s[rk + 1]] += 1rk += 1res = 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 -= 1left += 1#记录最大的窗口值res = max(res, i - left + 1 - d)#如果最大窗口值和数组长度相同，说明数组中没有0元素，又因必须删除一个元素，所以返回res-1if res == len(nums):return res - 1return res

1208

思路：使用变长滑动窗口，与1493差别不大。

class Solution:def equalSubstring(self, s: str, t: str, maxCost: int) -> int:changeCost = 0left = 0res = 0for 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 += 1res = max(res, i - left + 1)return res

2730

思路：与1493、1208相似，变长滑动窗口的不同运用。

class Solution:def longestSemiRepetitiveSubstring(self, s: str) -> int:res = 0left = 0p = 0if len(s) == 1:return 1for i in range(1,len(s)):if s[i] == s[i - 1]:p += 1while p > 1 and left < len(s) - 1:if s[left] == s[left + 1]:p -= 1left += 1res = max(res, i - left + 1)return res

904

思路：使用一个哈希表存储每次摘的水果，当采摘的水果种类大于2时，窗口的左端点向右一直移动，知道采摘的水果种类不超过2为止，然后记录每次移动左端或者右端后窗口的值，最大值即为答案。

class Solution:def totalFruit(self, fruits: List[int]) -> int:s = Counter()left = 0res = 0for i in range(len(fruits)):s[fruits[i]] += 1while len(s) > 2:#去掉最左端这个水果s[fruits[left]] -= 1#如果这个种类的水果数量为0了，就从篮子里删掉这一个种类if s[fruits[left]] == 0:del s[fruits[left]]left += 1res = max(res, i - left + 1)return res

1695

class Solution:def maximumUniqueSubarray(self, nums: List[int]) -> int:res = 0now = 0left = 0c = Counter()for i in range(len(nums)):c[nums[i]] += 1now += nums[i]while c[nums[i]] > 1 and left < i:c[nums[left]] -= 1now -= nums[left]left += 1res = max(res, now)return res

2958

class Solution:def maxSubarrayLength(self, nums: List[int], k: int) -> int:res = 0left = 0c = Counter()for i in range(len(nums)):c[nums[i]] += 1while c[nums[i]] > k and left < i:c[nums[left]] -= 1left += 1res = max(res, i - left + 1)return res

2779

class Solution:def maximumBeauty(self, nums: List[int], k: int) -> int:nums.sort()res = 0left = 0for i in range(len(nums)):while nums[i] - nums[left] > 2*k:left += 1res = max(res, i - left + 1)return res

2024

class Solution:def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:c = Counter()left = 0res = 0for i in range(len(answerKey)):c[answerKey[i]] += 1while min(c["T"], c["F"]) > k:c[answerKey[left]] -= 1left += 1res = max(res, i - left + 1)return res 

1004

class Solution:def longestOnes(self, nums: List[int], k: int) -> int:res = 0left = 0z = 0for i in range(len(nums)):if nums[i] == 0:z += 1while z > k:if nums[left] == 0:z -= 1left += 1res = max(res, i - left + 1)return res

1658

class Solution:def minOperations(self, nums: List[int], x: int) -> int:left = 0res = -1s = sum(nums) - xfor i in range(len(nums)):s -= nums[i]while s < 0 and left <= i:s += nums[left]left += 1if s == 0:res = max(res, i - left + 1)if res >= 0:return len(nums) - reselse: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 1nums.sort()left = 0res = 0now = 0for i in range(1,len(nums)):now += (nums[i] - nums[i - 1]) * (i - left)while now > k:now -= (nums[i] -nums[left])left += 1res = 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]] += 1print(c)if c['a'] < k or c['b'] < k or c['c'] < k:return -1res = 0left = -1for i in range(len(s)):c[s[i]] -= 1while c[s[i]] < k:left += 1c[s[left]] += 1res = max(res, i - left + 1)return n - res + 1

2831

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 = 0for pos in pos_lists.values():if len(pos) <= ans:continue  # 无法让 ans 变得更大left = 0for right, p in enumerate(pos):while p - pos[left] > k:  # 要删除的数太多了left += 1ans = max(ans, right - left + 1)return ans