1 字符串中的变位词
1.1 题目描述
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。
换句话说，第一个字符串的排列之一是第二个字符串的 子串 。
示例1:
输入: s1 = “ab” s2 = “eidbaooo”
输出: true
解释: s2 包含 s1 的排列之一 (“ba”).
示例2:
输入: s1= “ab” s2 = “eidboaoo”
输出: false
1.2 思路
类似滑动窗口的思路，但采用哈希表来存储窗口中的字符出现的次数，然后与字符串s1中的字符出现次数作比较，当完全相等时说明当前窗口内的字符串为s1的变位词，返回true,否则将窗口最左侧的字符从哈希表中去掉(对应字符的次数减1)、窗口最右侧字符加入到哈希表中（仍然为左闭右开区间）。
完整代码如下：
class Solution {
bool check(const int *a, const int *b){
for(int i = 0; i < 26; ++i){
if(a[i] == b[i]){
continue;
}
return false;
}
return true;
}
public:
bool checkInclusion(string s1, string s2) {
int len1 = s1.length(), len2 = s2.length();
if(len1 > len2) return false;
int hash1[26] = {0}, hash2[26] = {0};
for(int i = 0; i < len1; ++i){
hash1[s1[i] - 'a']++;
hash2[s2[i] - 'a']++;
}
for(int i = len1; i < len2; ++i){
if(check(hash1, hash2)){
return true;
}else{
hash2[s2[i] - 'a']++;
hash2[s2[i-len1] - 'a']--;
}
}
return check(hash1, hash2);
}
}; 2 字符串中的所有变位词
2.1 题目描述
给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
变位词 指字母相同，但排列不同的字符串。
示例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” 的变位词。
2.2 思路
思路同上一题，只不过这一题需要完全遍历完字符串s,当检测到滑动窗口中的字符串中字符出现次数与字符串p中字符出现次数完全一致时，说明窗口中的字符串为字符串p的变位词，将窗口左端点加入到答案数组中，遍历过程中重复将窗口最左侧元素去除并加入左右侧元素(左闭右开区间)。
完整代码如下：
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> res;
vector<int> hash_s(26, 0), hash_p(26, 0);
int slen = s.length(), plen = p.length();
if(slen < plen) return res;
for(int i = 0; i < plen; ++i){
hash_s[s[i] - 'a']++;
hash_p[p[i] - 'a']++;
}
if(hash_s == hash_p) res.emplace_back(0);
for(int i = plen; i < slen; ++i){
hash_s[s[i] - 'a']++;
hash_s[s[i - plen] - 'a']--;
if(hash_s == hash_p){
res.emplace_back(i - plen+1);
}
}
return res;
}
}; 3 不含重复字符的最长子字符串
3.1 题目描述
给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。
示例1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子字符串是 “abc”，所以其长度为 3。
示例2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子字符串是 “b”，所以其长度为 1。
示例3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。
示例4:
输入: s = “”
输出: 0
3.2 思路
滑动窗口典型题目，窗口的长度即为连续子字符串的长度，初始化长度为1，从而窗口左端点left = 0，右端点right = 1(窗口为左闭右开区间),然后进行遍历，右端点从1开始，循环遍历整个字符串，然后内循环窗口内的字符，当检测到窗口中的字符与s[right]相同时，将答案更新为当前窗口长度与原答案中的大者，并将窗口左端点更新为重叠位置的下个字符。
完整代码如下：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len = s.length();
if(len < 2) return len;
int ans = 1, left = 0, right = 1;
while(right < len){
for(int i = left; i < right; ++i){
if(s[i] == s[right]){
ans = max(ans, right - left);
left = i + 1;
break;
}
}
++right;
}
return max(ans, right - left);
}
};