(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,将窗口最左元素去除,维持窗口大小不变
判断字符个数数组是否相同。