传送门 https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
题目简述：
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 ：
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。
题解：
个人超时解法
class Solution {
public:
int max=0;
int notBelong(string s,char c){
int f=1;
for(int i=0;i<s.size();i++){
if(c==s[i]){
f=0;
break;
}
}
if(f==1)
return 1;
else
return 0;
}
int lengthOfLongestSubstring(string s) {
if(s.size()==0) //当s的长度为0或1时的出错情况任意忽视
return 0;
else if(s.size()==1)
return 1;
else
{
for(int i=0;i<s.size()-1;i++){
string str="";
str+=s[i];
for(int j=i+1;j<s.size();j++){
if(notBelong(str,s[j])){
str+=s[j];
}else{
if(str.size()>max)
max=str.size();
break;
}
}
if(str.size()>max)
max=str.size();
}
return max;
}
}
};
滑动窗口算法
思路：
窗口指由开始和结束索引i,j定义的一个集合。
将子串存入一个容器，如果s[j]不包含于子串中，向右滑动索引j，即j++;
如果s[j]包含于子串中，则i++，窗口缩小。其中，在j++之后，取ans和（j-i）的最大值，即在线得到子串长度的最大值。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n=s.size();
set<char> ss;
int ans=0,i=0,j=0;
while(i<n && j<n){
if(find(ss.begin(),ss.end(),s[j])==ss.end()){
ss.insert(s[j++]);
ans= ans>(j-i)? ans: j-i;
}else{
ss.erase(s[i++]);
}
}
return ans;
}
};
map法优化：
我们可以定义字符到索引的映射，而不是使用集合来判断一个字符是否存在。 当我们找到重复的字符时，我们可以立即跳过该窗口。
如果s[j]在[i,j)范围内有与j'重复的字符，不是逐渐增加i，而是直接跳过[i,j']的范围内的所有元素，将i变为j'+1。（注意取i和j'+1的较大值，eg：”abba”）
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n=s.size();
map<char,int> m;
int ans =0;
for(int j=0,i=0;j<n;j++){
if(m.find(s[j])!=m.end()){
i= m[s[j]]>i? m[s[j]]: i;
}
ans = ans > (j-i+1)? ans : (j-i+1);
m[s[j]]=j+1;
}
return ans;
}
};