题目描述

blablabla

算法1

(常用方法) $O(n)$

class Solution {
public:
    int longestSubstringWithoutDuplication(string s) {
        if(!s.size()) return 0;
        int n=s.size();
        map<char,int> a;
        int res=0;
        for(int i=0,j=0;i<s.size();i++)
        {
            a[s[i]]++;//map中存的是出现次数
            while(a[s[i]]>1)
            {

                a[s[j]]--;
                j++;
            }
            res=max(res,i-j+1);
        }
        return res;
    }
};

算法2

时间复杂度$O(n)$

C++ 代码

class Solution {
public:
    int longestSubstringWithoutDuplication(string s) {
        if(!s.size()) return 0;
        int n=s.size();
        int start=0;
        map<char,int> a;
        int res=0;
        int len=0;
        for(int i=0;i<n;i++)
        {
            if(a.find(s[i])!=a.end()&&a[s[i]]>=start)//map中存的是下标
    //一定要判断是否s[i]已存在map中，因为刚开始i=0,start=0时,满足a[s[i]]=0>=start，这时进入循环是错误的
            {
                start=a[s[i]]+1;
                len=i-start;
            }
            a[s[i]]=i;
            len++;
            res=max(res,len);
        }
        return res;
    }
};

算法3

(桶优化)

时间复杂度 $O(n)$

C++ 代码

class Solution {
public:
    int longestSubstringWithoutDuplication(string s) {
        if(!s.size()) return 0;
        int n=s.size();
        int start=0;
        vector<int> a(128,-1);//由于map无法初始化，数组中存的是下标
        int res=0;
        int len=0;
        for(int i=0;i<n;i++)
        {
            if(a[s[i]]>=start) //少一个判断是否已经有s[i]在哈希表里了
            {
                start=a[s[i]]+1;
                len=i-start;
            }
            a[s[i]]=i;
            len++;
            res=max(res,len);
        }
        return res;
    }
};