算法题每日一练---第67天：无重复字符的最长子串

一、问题描述

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

题目链接：无重复字符的最长子串。

二、题目要求

样例 1

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

样例 2

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

考察

1.字符串、滑动窗口
2.建议用时20~35min

三、问题分析

拿到这一题，首先确定属于字符串的应用，以样例 1为例，我一开始的思路是：

从字符串逐个开始遍历，依次向后寻找以当前字符作为首位的最大子串。

abcabcbb
第一位a             abc
第二位b             bca
第三位c             cab
第四位a             abc
......
最后一位b           b

我一开始的想法是哈希表（C++的map计数），如果当前这个字符前面的哈希表里面没有出现，那么字符串长度+1，这个字符哈希表+1。按照上面的步骤，逐步遍历。

但是这种算法效率也太差了，我们优化一下。

其实可以把原来的二层循环简化到一层，l r作为双指针分别指向第一个字符，依次向后遍历。

如果r指向字符没出现，将它后一位的下标加入哈希表中，l不变，r++。

如果r指向字符出现，l需要变成上一个出现的字符后一位，这样可以保障[l,r]区间内不存在重复的字符。

可以依照力扣上面的几张图示，帮助理解。

四、编码实现

1.优化前

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
    int i,j,n=s.size(),ans=0,k=0;//初始化代码
    map<char,int>m;//哈希表存储
    for(i=0;i<n;i++)//每一个字符作为起点
    {
        m.clear();//清空
        ans=0;//
        for(j=i;j<n;j++)//向后寻找无重复字符
        {
            if(m[s[j]]==0)//找到了
            {
                ans++;//计数
                m[s[j]]++;//标记
            }
            else//没找到直接退出
                break;
        }
        k=max(k,ans);//寻找最大值
    }
    return k;//输出结果
    }
};

2.优化后

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int l,r,n=s.size(),ans=0;//初始化变量
        map<char,int>m;//哈希表
        for(l=0,r=0;r<n;r++)//区间移动
        {
            if(m[s[r]]>0)//当前字符与哈希表里面冲突
                l=max(l,m[s[r]]);//l移位
            m[s[r]]=r+1;//哈希表存储下标的后一位
            ans=max(ans,r-l+1);//求出最大值
        }
        return ans;//输出结果
    }
};

五、测试结果

从964ms->12ms，不优化了，满足了。