/* 滑动窗口算法框架 */ void slidingWindow(string s, string t) { unordered_map<char, int> need, window; for (char c : t) need[c]++; int left = 0, right = 0; int valid = 0; while (right < s.size()) { // c 是将移入窗口的字符 char c = s[right]; // 右移窗口 right++; // 进行窗口内数据的一系列更新 ... /*** debug 输出的位置 ***/ printf("window: [%d, %d)\n", left, right); /********************/ // 判断左侧窗口是否要收缩 while (window needs shrink) { // d 是将移出窗口的字符 char d = s[left]; // 左移窗口 left++; // 进行窗口内数据的一系列更新 ... } } }
需要变化的地方
- 1、右指针右移之后窗口数据更新
- 2、判断窗口是否要收缩
- 3、左指针右移之后窗口数据更新
- 4、根据题意计算结果
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串
class Solution: def minWindow(self, s: str, t: str) -> str: target = collections.defaultdict(int) window = collections.defaultdict(int) for c in t: target[c] += 1 min_size = len(s) + 1 min_str = '' l, r, count, num_char = 0, 0, 0, len(target) while r < len(s): c = s[r] r += 1 if c in target: window[c] += 1 if window[c] == target[c]: count += 1 if count == num_char: while l < r and count == num_char: c = s[l] l += 1 if c in target: window[c] -= 1 if window[c] == target[c] - 1: count -= 1 if min_size > r - l + 1: min_size = r - l + 1 min_str = s[l - 1:r] return min_str
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 **s1 **的排列。
class Solution: def checkInclusion(self, s1: str, s2: str) -> bool: target = collections.defaultdict(int) for c in s1: target[c] += 1 r, num_char = 0, len(target) while r < len(s2): if s2[r] in target: l, count = r, 0 window = collections.defaultdict(int) while r < len(s2): c = s2[r] if c not in target: break window[c] += 1 if window[c] == target[c]: count += 1 if count == num_char: return True while window[c] > target[c]: window[s2[l]] -= 1 if window[s2[l]] == target[s2[l]] - 1: count -= 1 l += 1 r += 1 else: r += 1 return False
class Solution: def checkInclusion(self, s1: str, s2: str) -> bool: target = collections.defaultdict(int) for c in s1: target[c] += 1 r, num_char = 0, len(target) while r < len(s2): if s2[r] in target: l, count = r, 0 window = collections.defaultdict(int) while r < len(s2): c = s2[r] if c not in target: break window[c] += 1 if window[c] == target[c]: count += 1 if count == num_char: return True while window[c] > target[c]: window[s2[l]] -= 1 if window[s2[l]] == target[s2[l]] - 1: count -= 1 l += 1 r += 1 else: r += 1 return False
给定一个字符串 **s **和一个非空字符串 p，找到 **s **中所有是 **p **的字母异位词的子串，返回这些子串的起始索引。
class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: target = collections.defaultdict(int) for c in p: target[c] += 1 r, num_char = 0, len(target) results = [] while r < len(s): if s[r] in target: l, count = r, 0 window = collections.defaultdict(int) while r < len(s): c = s[r] if c not in target: break window[c] += 1 if window[c] == target[c]: count += 1 if count == num_char: results.append(l) window[s[l]] -= 1 count -= 1 l += 1 while window[c] > target[c]: window[s[l]] -= 1 if window[s[l]] == target[s[l]] - 1: count -= 1 l += 1 r += 1 else: r += 1 return results
class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: w_dict = {} n_dict = {} for p_s in p: if p_s not in n_dict: n_dict[p_s] = 1 w_dict[p_s] = 0 else: n_dict[p_s] += 1 p_len = len(p) s_len = len(s) left = 0 right = 0 result = [] while (left+p_len-1) <= s_len and right <= (s_len-1): new_s = s[right] if not new_s in n_dict: right += 1 for w_s in w_dict: w_dict[w_s] = 0 left = right else: w_dict[new_s] += 1 if (right-left+1) == p_len: if w_dict == n_dict: result.append(left) w_dict[s[left]] -= 1 left += 1 right += 1 return result
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: last_idx = {} l, max_length = 0, 0 for r, c in enumerate(s): if c in last_idx and last_idx[c] >= l: max_length = max(max_length, r - l) l = last_idx[c] + 1 last_idx[c] = r return max(max_length, len(s) - l) # note that the last substring is not judged in the loop
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: windows = {} length = len(s) left, right = 0, 0 output = 0 while left < length and right < length: if s[right] not in windows: windows[s[right]] = 1 else: windows[s[right]] += 1 while windows[s[right]] > 1: windows[s[left]] -= 1 left += 1 current = sum(windows.values()) if current > output: output = current right += 1 return output
- 和双指针题目类似，更像双指针的升级版，滑动窗口核心点是维护一个窗口集，根据窗口集来进行处理
- 核心步骤
- right 右移
- 收缩
- left 右移
- 求结果