滑窗问题【Leetcode3最长子串/438找出所有异位词】

本文主要是介绍滑窗问题【Leetcode3最长子串/438找出所有异位词】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
请注意，你的答案必须是子串的长度，子序列不是子串。

思路：滑窗范围[pl, pr)，用cnt数组维护滑窗内的每个字符的出现次数（实际上，不是1就是0）,对于即将进入滑窗中的字符s[pr]，如果滑窗中已经出现过了，那么pl右移缩小滑窗范围，使得s[pr]加入滑窗之后，s[pr]的出现次数仍为1，不会超出即可。

class Solution {
public:int lengthOfLongestSubstring(string s) {int cnt[130] = {0};int pl = 0, pr = 0, maxlen = 0, n = s.length();while (pr < n) {if (cnt[s[pr]] == 0) {cnt[s[pr]]++;pr++;} else {do {cnt[s[pl]]--;pl++;} while (s[pr] != s[pl - 1]);}if (maxlen < pr - pl)maxlen = pr - pl;}return maxlen;}
};

438. 找到字符串中所有字母异位词

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

思路：滑窗范围是[i, j)，对于每个即将加入滑窗的字符s[j]，看一下滑窗中该字符的个数（用cnts数组来维护），如果已经满了，那么滑窗左侧就要往右移动（缩小范围）了。

class Solution {int cntp[130], cnts[130];vector<int> ans;public:vector<int> findAnagrams(string s, string p) {int i = 0, j = 0, ns = s.length(), np = p.length();// 计算出p的每个字符的个数for (auto ch : p)cntp[ch]++;while (j <= ns) {if (cnts[s[j]] == cntp[s[j]]) // 满了{if (j - i == np)ans.push_back(i);while (s[i] != s[j]) {cnts[s[i]]--;i++;}cnts[s[i]]--;i++;}cnts[s[j]]++;j++;}return ans;}
};