Documentation Index
Fetch the complete documentation index at: https://base.bangwu.me/llms.txt
Use this file to discover all available pages before exploring further.
leetcode.3
The sliding window technique is a common two-pointer pattern for array and string problems. By maintaining a window that moves across the sequence, many problems can be solved in O(n) time.
Core idea
- Use two pointers,
left and right, to represent the window boundaries.
- Move
right to expand the window.
- When the window satisfies a shrink condition, move
left to contract it.
- Update the answer while the window changes.
Template code
def sliding_window(s: str):
left = 0
window = {} # 窗口内's 数据
result = 0
for right in range(len(s)):
# 1. 将right位置's 元素加入窗口
c = s[right]
window[c] = window.get(c, 0) + 1
# 2. 判断窗口是否需要收缩
while 窗口需要收缩's 条件:
# 3. 移出left位置's 元素
d = s[left]
left += 1
window[d] -= 1
# 4. 更新结果
result = max(result, right - left + 1)
return result
Classic problems
# leetcode.3 滑动窗口+哈希表
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
dic, res, i = {}, 0, -1
for j in range(len(s)):
if s[j] in dic:
i = max(i, dic[s[j]])
dic[s[j]] = j
res = max(res, j-i)
return res
class Solution:
def minWindow(self, s: str, t: str) -> str:
from collections import Counter
need = Counter(t)
window = {}
left = 0
valid = 0
start, length = 0, float('inf')
for right in range(len(s)):
c = s[right]
if c in need:
window[c] = window.get(c, 0) + 1
if window[c] == need[c]:
valid += 1
while valid == len(need):
if right - left + 1 < length:
start = left
length = right - left + 1
d = s[left]
left += 1
if d in need:
if window[d] == need[d]:
valid -= 1
window[d] -= 1
return "" if length == float('inf') else s[start:start+length]
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
from collections import Counter
need = Counter(p)
window = {}
left = 0
valid = 0
result = []
for right in range(len(s)):
c = s[right]
if c in need:
window[c] = window.get(c, 0) + 1
if window[c] == need[c]:
valid += 1
while right - left + 1 >= len(p):
if valid == len(need):
result.append(left)
d = s[left]
left += 1
if d in need:
if window[d] == need[d]:
valid -= 1
window[d] -= 1
return result
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
left = 0
total = 0
result = float('inf')
for right in range(len(nums)):
total += nums[right]
while total >= target:
result = min(result, right - left + 1)
total -= nums[left]
left += 1
return 0 if result == float('inf') else result
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
from collections import Counter
need = Counter(s1)
window = {}
left = 0
valid = 0
for right in range(len(s2)):
c = s2[right]
if c in need:
window[c] = window.get(c, 0) + 1
if window[c] == need[c]:
valid += 1
while right - left + 1 >= len(s1):
if valid == len(need):
return True
d = s2[left]
left += 1
if d in need:
if window[d] == need[d]:
valid -= 1
window[d] -= 1
return False
Typical use cases
- Finding the best value over a continuous subarray or substring
- String matching problems
- Fixed-length window problems
- Longest or shortest subarray satisfying a condition
Time complexity
Although there are two loops, each element is visited at most twice—once by right and once by left—so the overall time complexity is O(n).