【剑指offer-c++】jz48：最长不含重复字符的子字符串-爱代码爱编程

题目描述

描述：请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

数据范围: s.length≤40000。

输入："abcabcbb"
返回值：3
说明：因为无重复字符的最长子串是"abc"，所以其长度为 3。

输入："bbbbb"
返回值：1
说明：因为无重复字符的最长子串是"b"，所以其长度为 1。   

输入："pwwkew"
返回值：3
说明：因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。    

解题思路

最长不含重复字符的子字符串：最直观的想法是，使用变量i表示字符串起始位置，使用变量j表示字符串结束位置，i的范围是0~s.size()，j的范围是i~s.size()，每个起始位置轮次，创建一个无序集合unordered_set来存储从该起始位置开始不重复的字符，如果当前字符s[j]在uset中未出现过，那么就加入uset，反之则退出内层循环，同时计算字符串长度更新最长子字符串长度。其中有两点需要注意的地方：一个是当字符串只含有一个空格时，即s=" “，那么应该返回1，这是测试样例中的一个例子；另一个是j的作用域不应该只设置在内层for循环，因为有可能字符串遍历完，即j=s.size()，此时我们仍需要使用j-i来计算字符串长度，比如示例"df”，其应该返回的是2。

int lengthOfLongestSubstring(string s) 
{
    //空字符串
    if(s.size()==0)
       return 0;
    //测试结果样例
    if(s==" ")
       return 1;
    //res表示最长子字符串的长度
    int res=0; 
    //i表示起始位置
    for(int i=0;i<s.size();i++)
    {
       //用于存储不重复的字符
       unordered_set<char> uset;
       int j; 
       //j表示结束位置
       for(j=i;j<s.size();j++)
       {
          //元素第一次出现
          if(uset.count(s[j])==0)
             uset.emplace(s[j]);
          //元素重复出现
          else
             break;
       }
       //放在外面 因为j有可能等于字符串长度 比如df
       res=max(res,j-i);
     }
     return res;
}

优化：我们可以发现，上述方法每次出现重复时都是从下一个新的起始位置重新开始，这样时间复杂度以及空间复杂度都相对较高，我们可以使用滑动窗口来进行优化。滑动窗口是线性结构上的一段，类似于一个窗口，一般使用双指针来实现，左指针维护窗口左边界，右指针维护窗口右边界，两者同方向不同速率来维护窗口。初始左右指针均指向字符串起始位置字符，然后窗口右界向右移动，保证窗口内元素不重复，一旦元素重复，则将窗口左界向右收缩来保证窗口内元素不重复。具体做法如下：首先使用无序映射对unordered_map<char,int>来统计窗口内非重复元素以及对应次数；然后使用left表示左边界right表示右边界，初始两者均为0，边界条件是右边界right小于字符串长度，每次优先右边界右移即right++，接着记录右边界元素出现的次数，如果其次数大于1，那么表示右边界元素与前面元素重复，此时右移左边界，同时处理左边界元素对应出现的次数，直至当前右边界元素出现次数为1为止退出循环，并且更新窗口最大值即可。

int lengthOfLongestSubstring(string s) 
{
    //统计窗口内的字符以及相应次数
    unordered_map<char,int> umap; 
    //子字符串最大值
    int res=0;
    //设置窗口左右边界
    for(int left=0,right=0;right<s.size();right++)
    {
        //右边界元素出现次数加一
        umap[s[right]]++;
        //出现次数大于一则窗口内有重复
        while(umap[s[right]]>1)
        //窗口左移直至当前右边界元素次数为一同时减去左边界次数
           umap[s[left++]]--;
        //维护子串长度最大值 按照窗口左右边界计算
        res=max(res,right-left+1);
    }
    return res;
}

idea：使用unordered_map来记录窗口内的字符以及相应位置，使用dp[i]表示以第i个元素为结尾的字符串的最长非重复子串长度，其下标从1开始，而字符串下标从0开始，故dp[i]对应的是s[i-1]，从头开始遍历字符串，如果当前字符没有出现过，那么dp[i]=dp[i-1]+1，即当前最长等于前一个最长加一，反之如果当前字符出现过，那么dp[i]=min(dp[i-1]+1,i-umap[s[i-1]])，其中后者指的是当前最长等于当前位置减去当前元素上一次出现的位置，即表示不重复的长度，同时要防止中间出现重复元素，故要考虑上一个的基础，两者取最小值即可，最后每一次还要将当前元素以及对应位置加入哈希表，并且更新最长子串长度。

int lengthOfLongestSubstring(string s) 
{
    //统计窗口内的字符以及相应位置
    unordered_map<char,int> umap; 
    //子字符串最大值
    int res=0;
    //dp[i]表示以i为结尾的字符串的最长非重复子串
    vector<int> dp(s.size()+1,1);
    //为了方便递推公式设置dp[0]表示空串
    dp[0]=0;
    //dp[i]是第i个从1开始 但是字符串下标从0开始 故对应s[i-1]
    for(int i=1;i<=s.size();i++)
    {
       //如果当前字符没有出现过
       if(umap.find(s[i-1])==umap.end())
          //则以当前为结尾的最长等于前一个为结尾的最长加一
          dp[i]=dp[i-1]+1;
       //如果当前字符出现过
       else
          //则以当前为结尾的最长等于i减去上一次出现的位置
          //同时为了防止中间出现其他重复的字符需要考虑前一个基础
          dp[i]=min(dp[i-1]+1,i-umap[s[i-1]]);
       //将当前字符出现位置加入哈希表
       umap[s[i-1]]=i;
       //更新最长子字符串
       res=max(res,dp[i]);
    }
    return res;
}