LeetCode hot100-8

题目描述

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

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

示例 1:

输入: s = "abcabcbb"

输出: 3

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

示例 2:

输入: s = "bbbbb"

输出: 1

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

示例 3:

输入: s = "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。   请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

思路解析

        本题被划分到滑动窗口中,所以我主要讲解的是滑动窗口的思路,本题还有用数组下标记录出现重复位置的方法,代码与注释附在后面了, 感兴趣的话也可以看看

        首先定义一个左端点l与一个右端点r,当作滑动窗口的左右端点,并定义一个ans用于记录最长子串,我们每次将右端点向右移动一位,利用一个字符串str来记录当时滑动窗口中的子串,并用find函数判断新加入的元素是否已经存在于当前子串中,如果存在,更新ans并清空子串,左端点右移重复操作;如果不存在继续向窗口中添加新元素。

        注意：当最长子串的右端点为s最后一个元素时最长子串还存于str中，没有用来更新ans，所以在返回时需要返回的是str长度与ans之间的较大值。

代码实现

//滑动窗口
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size()==0)return 0;
        int l=0,r=0,ans=1;//滑动窗口为s[l]~s[r]
        string str="";//记录当前窗口子串
        while(r<s.size()){
            if(str.find(s[r])!=-1){//判断是否有重复值
                ans=max((int)str.size(),ans);//更新ans
                r=l=l+1;//移动窗口左端点
                str="";//清空子串
            }
            else str+=s[r++];//继续遍历s加长字串
        }
        //当最长子串的右端点为s最后一个元素时最长子串还存于str中，没有用来更新ans
        return max((int)str.size(),ans);
    }
};

//判断重复值
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int>str(128,-1);//该数组用来记录每个字符上一次出现的位置
        int len=0,start=0;//len记录最大子串长度，start记录无重复字符子串的开始位置
        for(int end=0;end<s.size();end++){
            if(str[s[end]]!=-1){
                start=max(start,str[s[end]]+1);//如果出现重复字符更新start
            }
            str[s[end]]=end;//更新当前字符的位置
            len=max(len,end-start+1);//当len小于当前子串长度更新len
        }
        return len;
    }
};