一般应用场景
数组，字符串子串等问题。
通用模板
双指针大致逻辑如下：
left = 0 right = 0 while right < len(s): # 右指针右移增大窗口 window.add(s[right]) right += 1 while isvalid: # 当满足某种条件时开始从左边收缩窗口 window.remove(s[left]) left += 1
代码模板：
def slidingWindow(s, t): from collections import defaultdict # defaultdict(int)对于不存在的键默认值为0， # 可以直接进行window[c] += 1的操作，免去了判断过程 window = defaultdict(int) needs = defaultdict(int) left = 0 right = 0 for c in t: needs[c] += 1 while right < len(s): # c1为移入窗口的字符 c1 = s[right] # 窗口右移 right += 1 # 进行窗口内数据的相关操作 # TODO # 判断左侧窗口是否要收缩 while window needs shrink: # c2为将要移出窗口的字符 c2 = s[left] # 左指针右移，收缩窗口 left += 1 # 进行窗口内数据的相关操作 # TODO
相关Leetcode题目
- 最小覆盖子串
class Solution: def minWindow(self, s: str, t: str) -> str: from collections import defaultdict needs = defaultdict(int) window = defaultdict(int) left = 0 right = 0 count = 0 #window中满足条件的字符数 start = 0 #记录最小子串的起始位置 min_len = float('inf') #记录最小子串的长度 for c in t: needs[c] += 1 while right < len(s): c1 = s[right] right += 1 if c1 in needs: window[c1] += 1 if window[c1] == needs[c1]: count += 1 while count == len(needs): # 更新最小覆盖子串 if right - left < min_len: start = left min_len = right - left c2 = s[left] left += 1 if c2 in needs: window[c2] -= 1 if window[c2] < needs[c2]: count -= 1 if min_len == float('inf'): return '' else: return s[start:start+min_len]
- 字符串排列
class Solution: def checkInclusion(self, s1: str, s2: str) -> bool: from collections import defaultdict needs = defaultdict(int) for c in s1: needs[c] += 1 window = defaultdict(int) left = 0 right = 0 count = 0 while right < len(s2): c1 = s2[right] right += 1 if c1 in needs: window[c1] += 1 if window[c1] == needs[c1]: count += 1 while count == len(needs): if right - left == len(s1): # 如果子串长度与s1相等则包含 return True c2 = s2[left] if c2 in needs: window[c2] -= 1 if window[c2] < needs[c2]: count -= 1 left += 1 return False
- 找所有字母异位词
class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: from collections import defaultdict needs = defaultdict(int) window = defaultdict(int) left = 0 right = 0 count = 0 res = [] for c in p: needs[c] += 1 while right < len(s): c1 = s[right] if c1 in needs: window[c1] += 1 if window[c1] == needs[c1]: count += 1 right += 1 while count == len(needs): if right - left == len(p): res.append(left) c2 = s[left] if c2 in needs: window[c2] -= 1 if window[c2] < needs[c2]: count -= 1 left += 1 return res
- 最长无重复子串
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: max_len = 0 left = 0 right = 0 n = len(s) from collections import defaultdict window = defaultdict(int) while right < n: c1 = s[right] right += 1 window[c1] += 1 while window[c1] > 1: c2 = s[left] left += 1 window[c2] -= 1 max_len = max(max_len, right - left) return max_len
