【LeetCode】3.无重复字符的最长字串 medium KMP双指针移动

3. 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。示例 1:
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

暴力解法

class Solution {
    
public:int lengthOfLongestSubstring(string s) {
    int num=0;for(int i=0;i<s.length();i++){
    int flag=1;int flagnum=0;vector<char> p;for(int j=i;j<s.length();j++){
    if(p.size()!=0){
    for(int z=0;z<p.size();z++){
    if(s[j]==p[z])flag=0;break;}}if(flag==0)break;while(flag){
    p.push_back(s[j]);flagnum++;}}if(flagnum>num)num=flagnum;}return num;}
};

双指针+哈希表

class Solution2 {
    
public:int lengthOfLongestSubstring(string s) {
    int start(0),end(0),length(0),result(0);int sSize=int(s.size());unordered_map<char,int> hash;while(end<sSize){
    char tmp=s[end];if(hash.find(tmp)!=hash.end()&&hash[tmp]>=start){
    start=hash[tmp]+1;length=end-start;}hash[tmp]=end;end++;length++;result=max(result,length);}return result;}
};//1228 滑动窗口 移动左边届直到哈希表里不存在重复元素
class Solution1 {
    
public:int lengthOfLongestSubstring(string s) {
    int left=0;int res=0;unordered_set<char> st; for(int i=0; i<s.size(); i++){
    while(st.find(s[i])!=st.end()){
    st.erase(s[left]);left++;}res=max(res,i-left+1);st.insert(s[i]);}return res;}
};class Solution {
    
public:int lengthOfLongestSubstring(string s) {
    int start=0;int curlen=0;int result=0;unordered_map<char, int> um;for(int i=0; i<s.size(); i++){
    if(um.find(s[i])!=um.end()&&um[s[i]]>=start){
    //这里要么判断当前字符的在哈希表里的下标有没有在start之前，要不需要用while不断跟新leftstart=um[s[i]]+1;}result=max(result,i-start+1);cout<<start<<" "<<i<<endl;um[s[i]]=i;}return result;}
};