LeetCode热题100——滑动窗口

窗口"/>

LeetCode热题100——滑动窗口

滑动窗口

• 1. 无重复字符的最长序列
• 2. 找对字符中所有字母的异位词

1. 无重复字符的最长序列

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

// 题解：利用set集合查询滑窗内是否存在重复字符
int lengthOfLongestSubstring(string s) {if (s.empty()) {return 0;}int max_length = 0;std::set<char> set_s;int left = 0;for (int i = 0; i < s.size(); ++i) {while (set_s.find(s[i]) != set_s.end()) {set_s.erase(s[left]);  // 移除最左边数据，指针+1left++;}set_s.insert(s[i]); // 窗口插入新数据max_length = std::max(max_length, i - left + 1);}return max_length;
}

2. 找对字符中所有字母的异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。

// 题解：由于不需要考虑字母顺序，因此可以通过词频的方式比较字母是否一致
vector<int> findAnagrams(string s, string p) {size_t s_length = s.size();size_t p_length = p.size();if (s_length < p_length) {return std::vector<int>();}std::vector<int> result;  // 保存结果std::vector<int> s_counts(26);  // 统计s序列的字母词频std::vector<int> p_counts(26);  // 统计p序列的字母词频for (size_t i = 0; i < p_length; ++i) {++s_counts[s[i] - 'a'];++p_counts[p[i] - 'a'];}// 比较首个字母词频是否一致if (s_counts == p_counts) {result.emplace_back(0);}// 滑动窗口比较字母词频for (size_t i = 0; i < s_length - p_length; ++i) {--s_counts[s[i] - 'a'];++s_counts[s[i + p_length] - 'a'];if (s_counts == p_counts) {result.emplace_back(i + 1);}}return result;
}