Sliding Window Fixed¶
Table of Contents¶
- 643. Maximum Average Subarray I (Easy)
- 219. Contains Duplicate II (Easy)
- 1456. Maximum Number of Vowels in a Substring of Given Length (Medium)
- 567. Permutation in String (Medium)
- 713. Subarray Product Less Than K (Medium)
- 1151. Minimum Swaps to Group All 1's Together (Medium) 👑
- 209. Minimum Size Subarray Sum (Medium)
- 76. Minimum Window Substring (Hard)
643. Maximum Average Subarray I¶
from typing import List
# Sliding Window Fixed Size
def findMaxAverage1(nums: List[int], k: int) -> float:
maxSum = float("-inf")
cur = 0
for idx, num in enumerate(nums):
cur += num
if idx < k - 1:
continue
maxSum = max(maxSum, cur)
cur -= nums[idx - k + 1]
return maxSum / k
# Sliding Window Fixed Size
def findMaxAverage2(nums: List[int], k: int) -> float:
n = len(nums)
if n == 1:
return float(nums[0])
cur = sum(nums[:k])
maxSum = cur
for i in range(k, n):
cur += nums[i] - nums[i - k]
maxSum = max(maxSum, cur)
return maxSum / k
nums = [1, 12, -5, -6, 50, 3]
k = 4
print(findMaxAverage1(nums, k)) # 12.75
print(findMaxAverage2(nums, k)) # 12.75
219. Contains Duplicate II¶
from typing import List
# Hash
def containsNearbyDuplicateHash(nums: List[int], k: int) -> bool:
hashmap = {} # num: last index
for idx, num in enumerate(nums):
if num in hashmap:
if idx - hashmap[num] <= k:
return True
hashmap[num] = idx
return False
# Sliding window - Fixed
def containsNearbyDuplicateWindow(nums: List[int], k: int) -> bool:
window = set()
left = 0
for right in range(len(nums)):
if right - left > k:
window.remove(nums[left])
left += 1
if nums[right] in window:
return True
window.add(nums[right])
return False
nums = [1, 2, 3, 1]
k = 3
print(containsNearbyDuplicateHash(nums, k)) # True
print(containsNearbyDuplicateWindow(nums, k)) # True
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int, int> last;
for (size_t i = 0; i < nums.size(); i++) {
int num = nums[i];
if (last.contains(num) && ((int)i - last[num] <= k)) return true;
last[num] = i;
}
return false;
}
bool containsNearbyDuplicateSlidingWindow(vector<int>& nums, int k) {
unordered_set<int> window;
for (size_t i = 0; i < nums.size(); i++) {
if (window.contains(nums[i])) return true;
window.insert(nums[i]);
if ((int)i - k >= 0) {
window.erase(nums[i - k]);
}
}
return false;
}
};
int main() {
Solution solution;
vector<int> nums = {1, 2, 3, 1};
assert(solution.containsNearbyDuplicate(nums, 3));
assert(solution.containsNearbyDuplicateSlidingWindow(nums, 3));
return 0;
}
1456. Maximum Number of Vowels in a Substring of Given Length¶
class maxVowels:
"""
Template problem for Fixed Size Sliding Window.
Technique: add-update-remove (入-更新-出)
"""
@staticmethod
def fixed_sliding_window(s: str, k: int) -> int:
res, cnt = 0, 0
for idx, ch in enumerate(s):
# ADD
if ch in "aeiou":
cnt += 1
# FORM
if idx < k - 1:
continue
# UPDATE
res = max(res, cnt)
# REMOVE
if s[idx - k + 1] in "aeiou":
cnt -= 1
return res
@staticmethod
def fixed_sliding_window_substring(s: str, k: int) -> int:
"""Sliding Window on Substring"""
vowels = set("aeiou")
n = len(s)
cnt, res = 0, 0
# init
for i in range(k):
if s[i] in vowels:
cnt += 1
res = cnt
# slide
for i in range(k, n):
if s[i] in vowels:
cnt += 1
if s[i - k] in vowels:
cnt -= 1
res = max(res, cnt)
return res
if __name__ == "__main__":
s = "abciiidef"
k = 3
assert maxVowels.fixed_sliding_window(s, k) == 3
assert maxVowels.fixed_sliding_window_substring(s, k) == 3
#include <cassert>
#include <string>
#include <unordered_set>
using namespace std;
class Solution {
public:
int maxVowels(string s, int k) {
int n = s.size();
int res = 0, cnt = 0;
unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
for (int right = 0; right < n; right++) {
if (vowels.count(s[right])) cnt++;
int left = right - k + 1;
if (left < 0) continue;
res = max(res, cnt);
if (vowels.count(s[left])) cnt--;
}
return res;
}
};
int main() {
Solution solution;
assert(solution.maxVowels("abciiidef", 3) == 3);
assert(solution.maxVowels("aeiou", 2) == 2);
return 0;
}
567. Permutation in String¶
def checkInclusion(s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
count1 = [0] * 26
count2 = [0] * 26
for i in range(len(s1)):
count1[ord(s1[i]) - ord("a")] += 1
count2[ord(s2[i]) - ord("a")] += 1
matches = 0
for i in range(26):
if count1[i] == count2[i]:
matches += 1
l = 0
for r in range(len(s1), len(s2)):
if matches == 26:
return True
index = ord(s2[r]) - ord("a")
count2[index] += 1
if count1[index] == count2[index]:
matches += 1
elif count1[index] + 1 == count2[index]:
matches -= 1
index = ord(s2[l]) - ord("a")
count2[index] -= 1
if count1[index] == count2[index]:
matches += 1
elif count1[index] - 1 == count2[index]:
matches -= 1
l += 1
return matches == 26
s1 = "ab"
s2 = "eidba"
print(checkInclusion(s1, s2)) # True
713. Subarray Product Less Than K¶
from typing import List
# Sliding Window Variable Subarrays Shorter
def numSubarrayProductLessThanK(nums: List[int], k: int) -> int:
if k <= 1:
return 0
left = 0
prod = 1
res = 0
for right in range(len(nums)):
prod *= nums[right]
while prod >= k:
prod //= nums[left]
left += 1
res += right - left + 1
return res
if __name__ == "__main__":
assert numSubarrayProductLessThanK([10, 5, 2, 6], 100) == 8
assert numSubarrayProductLessThanK([1, 2, 3], 0) == 0
assert numSubarrayProductLessThanK([1, 2, 3], 1) == 0
assert numSubarrayProductLessThanK([1, 2, 3], 2) == 1
assert numSubarrayProductLessThanK([1, 2, 3], 3) == 3
1151. Minimum Swaps to Group All 1's Together 👑¶
from typing import List
def minSwaps(data: List[int]) -> int:
n = len(data)
total = sum(data)
if total == 0 or total == 1 or total == n:
return 0
max_count = 0
cur = 0
left = 0
for right in range(n):
cur += data[right]
if right - left + 1 > total:
cur -= data[left]
left += 1
max_count = max(max_count, cur)
return total - max_count
data = [1, 0, 1, 0, 1]
print(minSwaps(data)) # 1
209. Minimum Size Subarray Sum¶
import bisect
from typing import List
# Prefix Sum
def minSubArrayLenPS(target: int, nums: List[int]) -> int:
n = len(nums)
prefix_sums = [0] * (n + 1)
for i in range(1, n + 1):
prefix_sums[i] = prefix_sums[i - 1] + nums[i - 1]
minLen = float("inf")
for i in range(n + 1):
new_target = target + prefix_sums[i]
bound = bisect.bisect_left(prefix_sums, new_target)
if bound != len(prefix_sums):
minLen = min(minLen, bound - i)
return 0 if minLen == float("inf") else minLen
# Sliding Window Variable Size
def minSubArrayLenSW(target: int, nums: List[int]) -> int:
res, cur = float("inf"), 0
left = 0
for right in range(len(nums)):
cur += nums[right]
while cur >= target:
res = min(res, right - left + 1)
cur -= nums[left]
left += 1
return res if res != float("inf") else 0
target = 7
nums = [2, 3, 1, 2, 4, 3]
print(minSubArrayLenPS(target, nums)) # 2
print(minSubArrayLenSW(target, nums)) # 2
76. Minimum Window Substring¶
from collections import Counter
def minWindow(s: str, t: str) -> str:
if not t or not s:
return ""
counts = Counter(t)
required = len(counts)
left, right = 0, 0
formed = 0
window_counts = dict()
result = float("inf"), None, None
while right < len(s):
char = s[right]
window_counts[char] = window_counts.get(char, 0) + 1
if char in counts and window_counts[char] == counts[char]:
formed += 1
while left <= right and formed == required:
char = s[left]
if right - left + 1 < result[0]:
result = (right - left + 1, left, right)
window_counts[char] -= 1
if char in counts and window_counts[char] < counts[char]:
formed -= 1
left += 1
right += 1
return "" if result[0] == float("inf") else s[result[1] : result[2] + 1]
s = "ADOBECODEBANC"
t = "ABC"
print(minWindow(s, t)) # BANC