[TOC] ## 示例 #### [239\. 滑动窗口最大值](https://leetcode-cn.com/problems/sliding-window-maximum/) 给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最大值。 ``` class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> result; if (nums.size() == 0 || k <= 0) return result; deque<int> q; // 双端队列 for (int i = 0; i < nums.size(); i++) { while (!q.empty() && (nums[q.back()] <= nums[i])) q.pop_back(); q.push_back(i); if (q.front() == i - k) q.pop_front(); if (i >= k - 1) result.push_back(nums[q.front()]); } return result; } }; ``` #### [76\. 最小覆盖子串](https://leetcode-cn.com/problems/minimum-window-substring/) 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。 示例： 输入: S = "ADOBECODEBANC", T = "ABC" 输出: "BANC" 说明： * 如果 S 中不存这样的子串，则返回空字符串 ""。 * 如果 S 中存在这样的子串，我们保证它是唯一的答案。 ``` class Solution { public: string minWindow(string s, string t) { if (t.size() > s.size()) return ""; map<char, int> win; map<char, int> need; for (auto& c : t) need[c]++; int left = 0, right = 0; int start = -1, end = s.size(); int matched = 0; while (right < s.size()) { char c = s[right]; if (need.find(c) != need.end()) { win[c]++; if (win[c] == need[c]) matched++; } while (matched == need.size()) { if (end - start > right - left) { start = left; end = right; } char a = s[left]; if (need.find(a) != need.end()) { if (win[a] == need[a]) matched--; win[a]--; } left++; } right++; } return start == -1 ? "" : s.substr(start, end - start + 1); } }; ``` #### [567\. 字符串的排列](https://leetcode-cn.com/problems/permutation-in-string/) 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。 换句话说，第一个字符串的排列之一是第二个字符串的子串。 示例1: 输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba"). 示例2: 输入: s1= "ab" s2 = "eidboaoo" 输出: False ``` class Solution { public: bool checkInclusion(string s1, string s2) { map<char, int> win; map<char, int> need; for (int i = 0; i < s1.size(); i++) { need[s1[i]]++; } int left = 0; int right = 0; int matched = 0; while (right < s2.size()) { char c = s2[right++]; if (need.find(c) != need.end()) { win[c]++; if (win[c] == need[c]) matched++; } // 当窗口长度等于字符串长度，缩紧窗口，可保证当前窗口大小不大于字符串窗口 if (right - left == s1.size()) { // 匹配 if (matched == need.size()) return true; char d = s2[left++]; if (need.find(d) != need.end()) { if (win[d] == need[d]) matched--; win[d]--; } } } return false; } }; ``` #### [438\. 找到字符串中所有字母异位词](https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/) 给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。 字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。其实和上一题是一样的。 说明： 字母异位词指字母相同，但排列不同的字符串。(注意：只考虑是否有相同字母) 不考虑答案输出的顺序。 示例 1: 输入: s: "cbaebabacd" p: "abc" 输出: [0, 6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。  示例 2: 输入: s: "abab" p: "ab" 输出: [0, 1, 2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。 ``` class Solution { public: vector<int> findAnagrams(string s, string p) { vector<int> result; map<char, int> win; map<char, int> need; for (int i = 0; i < p.size(); i++) { need[p[i]]++; } int left = 0; int right = 0; int matched = 0; while (right < s.size()) { char c = s[right++]; if (need.find(c) != need.end()) { win[c]++; if (win[c] == need[c]) matched++; } if (right - left == p.size()) { if (matched == need.size()) result.push_back(left); char d = s[left++]; if (need.find(d) != need.end()) { if (win[d] == need[d]) matched--; win[d]--; } } } return result; } }; ``` #### [3\. 无重复字符的最长子串](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/) 给定一个字符串，请你找出其中不含有重复字符的 **最长子串 **的长度。 ``` class Solution { public: int lengthOfLongestSubstring(string s) { map<char, int> win; int left = 0; int right = 0; int maxLen = 0; while (right < s.size()) { char c = s[right++]; win[c]++; while (win[c] > 1) // 窗口有重复字母，收缩 { win[s[left++]]--; } if (right - left > maxLen) maxLen = right - left; } return maxLen; } }; ```