滑动窗口

1、无重复字符的最长子串

（1）题目描述以及输入输出

(1)题目描述:
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。
(2)输入输出描述：
输入: s = "abcabcbb"
输出: 3 关键思路：
通过vector记录字符串中每个字符上次出现的位置，字符的ASCII作为索引，出现的位置作为记录值。
遍历字符串，每次滑动窗口内添加一个字符，都会更新left的值，使得left指向该位置后窗口内无重复值

（2）代码块

class Solution {
public:int lengthOfLongestSubstring(string s){int left = 0;int right = 0;int max_size = 0;vector<int> record(128,-1);			// 记录字符串中每个字符上次出现的位置for(;right<s.length();++right){left = max(left,record[s[right]]+1);	// 更新左窗口位置，使得窗口内无重复值max_size = max(max_size,right-left+1);	// 计算窗口大小record[s[right]] = right;       		// 更新当前字符的出现位置}return max_size;}
};

2、找到字符串中所有字母的异位词

（1）题目描述以及输入输出

(1)题目描述:
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
(2)输入输出描述：
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]关键思路：
定义两个vector统计两个字符串中字符出现个数，先统计p.length个
接着从s的第p.length进行遍历，每次遍历将窗口最右的字符出现个数统计进vector,将窗口最左元素去除，维持窗口大小不变
判断字符个数数组是否相同。

（2）代码块

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> s_record(26,0);vector<int> p_record(26,0);vector<int> result;int i = 0;for(i = 0;i<p.length();++i){s_record[s[i] - 'a']++;p_record[p[i] - 'a']++;}if(s_record == p_record)result.push_back(0);for(;i<s.length();++i){s_record[s[i] - 'a']++;s_record[s[i-p.length()] - 'a']--;if(s_record == p_record)result.push_back(i-p.length()+1);}return result;}
};