解题思路:看到重复用哈希表 本题用哈希表和滑动窗口滑动窗口用两个指针表示, 哈希表用来存储无重复的值,如果遍历哈希表找到了则说明这是重复的 需要移动这个窗口 滑动窗口向右移(用while循环),然后插入这个值,最终取最大的长度。
当右指针 right 遍历字符串时,检查当前字符 s[right] 是否已经在窗口中。然后在分为两种情况来考虑。
class Solution {
public:int lengthOfLongestSubstring(string s) {int sum = 0,left = 0;unordered_set<char> window;for(int right = 0; right < s.size();right++){while(window.find(s[right]) != window.end()){window.erase(s[left]);left++;}window.insert(s[right]);sum = max(sum,right-left+1); }return sum;}
};
解题思路:
用滑动窗口来解决 然后返回滑动窗口左指针。首先遍历p的所有字母,保存在一个数组中(下标表示字母,值表示字母出现的次数),然后处理s的数组,判断左指针是否小于0 即确定窗口大小是否符合标准标准了,符合标准之后就是比较两个数组是否相等 相等就是放入结果中。(这里面要处理s数组中的值 当left走了就要减减)。
class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int>result;vector<int>conts(26);vector<int>contp(26);for(char c:p){contp[c-'a']++;}for(int right = 0; right < s.size();right++){conts[s[right]-'a']++;//右端字母进入窗口int left = right - p.size() + 1;if(left<0)continue;//窗口长度不足 即只有刚开始时有if(conts == contp){//s和p相等result.push_back(left);//左端下标加入答案}conts[s[left]-'a']--;//左端字母离开窗口}return result;}
};