无重复字符的最长子串--滑动窗口

0x01.问题

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

int lengthOfLongestSubstring(string s)

0x02.简要分析

题目描述很简单，思路也很多，不过不同的思路，时间和空间的消耗差距巨大。

首先看一下第一种非常暴力的去判断每个子串：

class Solution {
public:
    bool isUnique(string astr) {
        unordered_map<char,int> table;
        for(char a:astr){
            if(table[a]==0) table[a]++;
            else return false;
        }
        return true;
    }

    int lengthOfLongestSubstring(string s) {
        int ans=0;
        int n=s.size();
        for(int i=0;i<n;i++){
            for(int j=1;j<=n-i;j++){
                if(isUnique(s.substr(i,j))) ans=max(ans,j);
            }
        }
        return ans;
    }
};

总得时间复杂度是O（N^3），毫无疑问，超时了。

经过分析，我们可以对这种算法进行一些小的优化，不需要判断每个子串，只需要判断每个新字符是否在之前出现过就行了，于是改进如下：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans=0;
        int n=s.size(),i,j;
        if(n==0) return 0;
        for(i=0;i<n;i++){
            unordered_map<char,int> table;
            table[s[i]]++;
            for(j=i+1;j<n;j++){
                if(table[s[j]]==0) table[s[j]]++;
                else{
                    ans=max(ans,j-i);
                    break;
                }
            }
            if(j==n) ans=max(ans,j-i);
        }
        return ans;
    }
};

时间复杂度为O（N^2），虽然过了，但是时间的消耗还是比较大的。

在这里，我们可以考虑使用滑动窗口，滑动窗口就是两个指针控制一段区域，不断的滑动，在这里，我们使用滑动窗口的思路就是：

• 使用一个指针i控制一个子字符串的起始。
• 一个指针j控制一个子串的结束。
• 使用map对已出现的字符进行记录。
• 每遇到一个新字符，判断是否在现在的子串区域内。
• 若在，则更新i为重复出现的的那个字符的下一个位置。
• 直到j遍历完字符串。

这里有些小细节需要注意：

• 每次更新的i应该取max(map[a],i)，目的是保证i是向前移动的。
• 这个步骤其实也消除了对跳过区域的map的删除操作。

0x03.解决代码–滑动窗口

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans=0,i,j;
        int n=s.size();
        unordered_map<char,int> hash;
        for(i=0,j=0;j<n;j++){
            if(hash.find(s[j])!=hash.end()){
                i=max(hash[s[j]],i);
            }
            ans=max(ans,j-i+1);
            hash[s[j]]=j+1;
        }
        return ans;
    }
};

时间复杂度为O（N），空间复杂度为O（min(M,N)）

ATFWUS --Writing By 2020–03–31