1.2 不定长滑动窗口
约 3782 字大约 13 分钟
2024-11-01
1.2.1 求最长/最大
提示
阿囧说：代码实操中，使用双指针left和right，right先滑到k个窗口大小，满足题目条件时停止，left开始向右移直到满足另一个条件，更新结果，再入循环
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: cnt = Counter() left = 0 res = 0 for right, c in enumerate(s): cnt[c] += 1 while cnt[c] > 1: cnt[s[left]] -= 1 left += 1 res = max(res, right - left + 1) return res时间复杂度：O(n)
空间复杂度：O(1)，本题中字符均为 ASCII 字符，所以空间复杂度 ≤ O(128)
class Solution: def maximumLengthSubstring(self, s: str) -> int: cnt = Counter() left = 0 res = 0 for right, c in enumerate(s): cnt[c] += 1 while cnt[c] > 2: cnt[s[left]] -= 1 left += 1 res = max(res, right - left + 1) return res时间复杂度：O(n)
空间复杂度：O(1)，本题中字符均为 ASCII 字符，所以空间复杂度 ≤ O(128)
class Solution: def longestSubarray(self, nums: List[int]) -> int: left = 0 cnt = Counter() res = 0 for right, num in enumerate(nums): cnt[num] += 1 while cnt[0] >= 2: cnt[nums[left]] -= 1 left += 1 res = max(res, right - left + 1 - cnt[0]) return res if cnt[0] else len(nums) - 1时间复杂度：O(n)
空间复杂度：O(1)，本题中字符均为 0 or 1 字符，所以空间复杂度 ≤ O(2)
class Solution: def equalSubstring(self, s: str, t: str, maxCost: int) -> int: cost = [] for c1, c2 in zip(s, t): cost.append(abs(ord(c1) - ord(c2))) left = 0 res = 0 sum_cost = 0 for right, num in enumerate(cost): sum_cost += num while sum_cost > maxCost: sum_cost -= cost[left] left += 1 res = max(res, right - left + 1) return res时间复杂度：O(n)
空间复杂度：O(n)，cost列表的大小与输入字符串的长度相同都是 n
class Solution: def longestSemiRepetitiveSubstring(self, s: str) -> int: left = 0 res = 1 same = 0 for right in range(1, len(s)): if s[right] == s[right - 1]: same += 1 if same == 2: left += 1 while s[left] != s[left - 1]: left += 1 same = 1 res = max(res, right - left + 1) return res时间复杂度：O(n)
空间复杂度：O(1)，常量辅助空间
class Solution: def totalFruit(self, fruits: List[int]) -> int: left = 0 res = 0 cnt = Counter() for right, fruit in enumerate(fruits): cnt[fruit] += 1 while len(cnt) > 2: cnt[fruits[left]] -= 1 if cnt[fruits[left]] == 0: del cnt[fruits[left]] left += 1 res = max(res, right - left + 1) return res时间复杂度：O(n)
空间复杂度：O(1)，cnt只会存储 2 种水果
class Solution: def maximumUniqueSubarray(self, nums: List[int]) -> int: left = 0 res = 0 temp = 0 cnt = Counter() for right, num in enumerate(nums): cnt[num] += 1 temp += num while cnt[num] > 1: cnt[nums[left]] -= 1 temp -= nums[left] left += 1 res = max(res, temp) return res时间复杂度：O(n)
空间复杂度：O(k)， k 是 nums 中不重复元素的数量
class Solution: def maxSubarrayLength(self, nums: List[int], k: int) -> int: left = 0 res = 0 cnt = Counter() for right, num in enumerate(nums): cnt[num] += 1 while cnt[num] > k: cnt[nums[left]] -= 1 left += 1 res = max(res, right - left + 1) return res时间复杂度：O(n)
空间复杂度：O(m)， m 是 nums 中不重复元素的数量
class Solution: def maximumBeauty(self, nums: List[int], k: int) -> int: left = 0 res = 0 nums = sorted(nums) for right in range(len(nums)): while nums[left] + k < nums[right] - k: left += 1 res = max(res, right - left + 1) return res时间复杂度：O(nlogn)，其中 n 为 nums 的长度。瓶颈在排序上。虽然写了个二重循环，但是内层循环中对 left 加一的总执行次数不会超过 n 次，所以滑窗那部分的时间复杂度为 O(n)
空间复杂度：O(1)，忽略排序的栈开销，仅用到若干额外变量
class Solution: def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int: left = 0 res = 0 cnt = Counter() for right, c in enumerate(answerKey): cnt[c] += 1 while cnt['T'] > k and cnt['F'] > k: cnt[answerKey[left]] -= 1 left += 1 res = max(res, right - left + 1) return res时间复杂度：O(n)
空间复杂度：O(1)
class Solution: def longestOnes(self, nums: List[int], k: int) -> int: left = 0 res = 0 from collections import Counter cnt = Counter() for right, num in enumerate(nums): cnt[num] += 1 while cnt[0] > k: cnt[nums[left]] -= 1 left += 1 res = max(res, right - left + 1) return res时间复杂度：O(n)
空间复杂度：O(1)
class Solution: def minOperations(self, nums: List[int], x: int) -> int: sum_nums = sum(nums) print(sum_nums) if sum_nums < x: return -1 target = sum_nums - x left = 0 temp = 0 res = -1 for right, num in enumerate(nums): temp += num while temp > target: temp -= nums[left] left += 1 if temp == target: res = max(res, right - left + 1) return -1 if res < 0 else len(nums) - res时间复杂度：O(n)
空间复杂度：O(1)
class Solution: def maxFrequency(self, nums: List[int], k: int) -> int: left = 0 temp = 0 res = 0 nums.sort() for right, num in enumerate(nums): temp += num while temp + k < num * (right - left + 1): temp -= nums[left] left += 1 res = max(res, right - left + 1) return res时间复杂度：O(nlogn)，对 nums 数组进行排序的时间复杂度是 O(nlogn)，其中 n 是数组的长度。
空间复杂度：O(1)
我的思路：s = "aabaaaacaabc", k = 2，cnt记录s中a、b、c出现的次数（Counter({'a': 8, 'b': 2, 'c': 2})），每一个value减去k后就是子串各字符的上限值（Counter({'a': 6, 'b': 0, 'c': 0})），目标是找到小于等于cnt的最长子串（"aaaa"），cnt2记录窗口内字符出现的次数
class Solution: def takeCharacters(self, s: str, k: int) -> int: left = 0 res = 0 cnt = Counter(s) if cnt['a'] < k or cnt['b'] < k or cnt['c'] < k: return -1 cnt2 = Counter() for key, value in cnt.items(): cnt[key] -= k for right, c in enumerate(s): cnt2[c] += 1 while cnt2['a'] > cnt['a'] or cnt2['b'] > cnt['b'] or cnt2['c'] > cnt['c']: cnt2[s[left]] -= 1 left += 1 res = max(res, right - left + 1) return len(s) - res时间复杂度：O(n)
空间复杂度：O(1)，本题只有三种字符
灵神的思路：与其维护窗口内的字母个数，不如直接维护窗口外的字母个数，这也是我们取走的字母个数。
class Solution: def takeCharacters(self, s: str, k: int) -> int: cnt = Counter(s) # 一开始，把所有字母都取走 if any(cnt[c] < k for c in "abc"): return -1 # 字母个数不足 k mx = left = 0 for right, c in enumerate(s): cnt[c] -= 1 # 移入窗口，相当于不取走 c while cnt[c] < k: # 窗口之外的 c 不足 k cnt[s[left]] += 1 # 移出窗口，相当于取走 s[left] left += 1 mx = max(mx, right - left + 1) return len(s) - mx时间复杂度：O(n)
空间复杂度：O(1)，本题只有三种字符
1.2.2 求最短/最小
class Solution: def minSubArrayLen(self, target: int, nums: List[int]) -> int: left = 0 res, temp = float('inf'), 0 for right, num in enumerate(nums): temp += num while temp >= target: res = min(res, right - left + 1) temp -= nums[left] left += 1 return 0 if res == float('inf') else res时间复杂度：O(n)
空间复杂度：O(1)
垃圾题目毁我青春class Solution: def shortestBeautifulSubstring(self, s: str, k: int) -> str: if s.count('1') < k: return '' res = s cnt_1 = left = 0 for right, c in enumerate(s): cnt_1 += int(c) while cnt_1 > k or s[left] == '0': cnt_1 -= int(s[left]) left += 1 if cnt_1 == k: temp = s[left: right + 1] if (len(temp) == len(res) and temp < res) or len(temp) < len(res): res = temp return res时间复杂度：O(n2)
空间复杂度：O(n) 或 O(1)。字符串切片需要 O(n) 的空间，Go 除外。
1.2.3 求子数组个数
1.2.3.1 越长越合法
提示
一般要写 res += left。
滑动窗口的内层循环结束时，右端点固定在 right，左端点在 0,1,2,3,...,left - 1 的所有子数组（子串）都是合法的，这一共 left 个。即窗口左边的子串
class Solution: def numberOfSubstrings(self, s: str) -> int: cnt = Counter() left, res = 0, 0 for i, c in enumerate(s): cnt[c] += 1 while cnt['a'] > 0 and cnt['b'] > 0 and cnt['c'] > 0: cnt[s[left]] -= 1 left += 1 print(left) res += left return res时间复杂度：O(n)
空间复杂度：O(1)
class Solution: def countSubarrays(self, nums: List[int], k: int) -> int: left = 0 res = 0 max_num_cnt = 0 max_num = max(nums) for right, num in enumerate(nums): if num == max_num: max_num_cnt += 1 while max_num_cnt == k: if nums[left] == max_num: max_num_cnt -= 1 left += 1 res += left return res时间复杂度：O(n)
空间复杂度：O(1)
class Solution: def numberOfSubstrings(self, s: str, k: int) -> int: left = 0 cnt = Counter() res = 0 for right, c in enumerate(s): cnt[c] += 1 while k in cnt.values(): cnt[s[left]] -= 1 left += 1 res += left return res时间复杂度：O(n)
空间复杂度：O(1)
class Solution: def countCompleteSubarrays(self, nums: List[int]) -> int: nums_class = len(set(nums)) left = 0 res = 0 cnt = Counter() for right, num in enumerate(nums): cnt[num] += 1 while len(cnt.values()) == nums_class: cnt[nums[left]] -= 1 if cnt[nums[left]] == 0: del cnt[nums[left]] left += 1 res += left return res时间复杂度：O(n)
空间复杂度：O(1)
难点：如何记录成对元素的个数？有点数学技巧在里面，比如 nums = [1,1,1,1,1], k = 10，从第二个 1 开始，滑动窗口每增加一个 1 ，成对数量 = 当前成对数量 + 之前窗口元素个数。举例：[1,1] 是 1 对，[1,1,1] 是 1 + 2 = 3 对，[1,1,1,1] 是 3 + 3 = 6 对
class Solution: def countGood(self, nums: List[int], k: int) -> int: left = 0 cnt = defaultdict(int) res = 0 pairs = 0 for right, num in enumerate(nums): pairs += cnt[num] cnt[num] += 1 while pairs >= k: cnt[nums[left]] -= 1 pairs -= cnt[nums[left]] left += 1 res += left return res时间复杂度：O(n)
空间复杂度：O(n)
1.2.3.2 越短越合法
提示
一般要写 res += right - left + 1。
滑动窗口的内层循环结束时，右端点固定在 right，左端点在 left, left + 1, ..., right 的所有子数组（子串）都是合法的，这一共 right - left + 1 个。即窗口内的子串
class Solution: def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int: left = 0 res = 0 temp = 1 if k <= 1: return 0 for right, num in enumerate(nums): temp *= num while temp >= k: temp /= nums[left] left += 1 res += right - left + 1 return res时间复杂度：O(n)
空间复杂度：O(1)
class Solution: def countKConstraintSubstrings(self, s: str, k: int) -> int: left = 0 res = 0 cnt = Counter() for right, c in enumerate(s): cnt[c] += 1 while cnt['0'] > k and cnt['1'] > k: cnt[s[left]] -= 1 left += 1 res += right - left + 1 return res时间复杂度：O(n)
空间复杂度：O(1)
class Solution: def countSubarrays(self, nums: List[int], k: int) -> int: left = 0 res = 0 temp = 0 for right, num in enumerate(nums): temp += num while temp * (right - left + 1) >= k: temp -= nums[left] left += 1 res += right - left + 1 return res时间复杂度：O(n)
空间复杂度：O(1)
我的解法：输麻了，复杂度会惩罚每一个不用模板的人- 时间复杂度太高了，max(temp) 和 min(temp) 都是线性时间复杂度的操作，分别需要遍历整个数组 temp 来找出最大值和最小值。因此，在最坏情况下，每次对 temp 数组的操作的时间复杂度是 O(n)，其中 n 是 temp 的长度。移除数组的第一个元素（通过 temp = temp[1:]），这也是一个 O(n) 的操作，因为每次都要更新 temp 数组。
- 对于每个 right（即每个元素），在最坏的情况下，max(temp) 和 min(temp) 的计算需要 O(n) 时间，因此整个算法的时间复杂度是 O(n²)，其中 n 是数组的长度。
class Solution: def continuousSubarrays(self, nums: List[int]) -> int: res = 0 temp = [] for right, num in enumerate(nums): temp.append(num) while max(temp) - min(temp) > 2: temp = temp[1:] res += len(temp) return res时间复杂度：O(n2)
空间复杂度：O(n)
换上模板
class Solution: def continuousSubarrays(self, nums: List[int]) -> int: res = 0 left = 0 from collections import Counter cnt = Counter() for right, num in enumerate(nums): cnt[num] += 1 while max(cnt) - min(cnt) > 2: cnt[nums[left]] -= 1 if cnt[nums[left]] == 0: del cnt[nums[left]] left += 1 res += right - left + 1 return res时间复杂度：O(n)
空间复杂度：O(1)
1.2.3.3 恰好型滑动窗口
提示
例如，要计算有多少个元素和恰好等于k的子数组，可以把问题变成:
- 计算有多少个元素和 ≥ k的子数组。
- 计算有多少个元素和 > k，也就是 ≥ k+1的子数组。
答案就是元素和 ≥ k的子数组个数，减去元素和 ≥ k+1 的子数组个数。这里把>转换成≥，从而 可以把滑窗逻辑封装成一个函数 f ，然后用 f(k)-f(k + 1)计算，无需编写两份滑窗代码。
总结:「恰好」可以拆分成两个「至少」，也就是两个「越长越合法」的滑窗问题。
注:也可以把问题变成 ≤ k减去 ≤ k-1(两个至多)。可根据题目选择合适的变形方式。
注:也可以把两个滑动窗口合并起来，维护同一个右端点 right 和两个左端点 left1 和 left2，我把这种写法叫做三指针滑动窗口
越长越合法，元素和 ≥ k的子数组个数，减去元素和 ≥ k+1 的子数组个数
class Solution: def numSubarraysWithSum(self, nums: List[int], goal: int) -> int: def helper(k): left = 0 res = 0 temp = 0 for right, num in enumerate(nums): temp += num while temp >= k and left <= right: temp -= nums[left] left += 1 res += left return res return helper(goal) - helper(goal+1)时间复杂度：O(n)
空间复杂度：O(1)
越短越合法，元素和 ≤ k的子数组个数，减去元素和 ≤ k-1 的子数组个数
class Solution: def numSubarraysWithSum(self, nums: List[int], goal: int) -> int: def helper(k): left = 0 res = 0 temp = 0 for right, num in enumerate(nums): temp += num while temp > k and left <= right: temp -= nums[left] left += 1 res += right - left + 1 return res return helper(goal) - helper(goal-1)时间复杂度：O(n)
空间复杂度：O(1)
越长越合法，元素和 ≥ k的子数组个数，减去元素和 ≥ k+1 的子数组个数
class Solution: def numberOfSubarrays(self, nums: List[int], k: int) -> int: def helper(k): left = 0 res = 0 odd = 0 for right, num in enumerate(nums): if num % 2 == 1: odd += 1 while odd >= k: if nums[left] % 2 == 1: odd -= 1 left += 1 res += left return res return helper(k) - helper(k+1)时间复杂度：O(n)
空间复杂度：O(1)