欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leecode3——无重复字符的最长子串

程序员文章站 2022-07-12 12:10:15
...

题目说明:
如,在”abcabcbb”中,其无重复字符的最长子字符串是”abc”,其长度为 3;
对于,”bbbbb”,其无重复字符的最长子字符串为”b”,长度为1。
基本思路:
遍历该字符串,往集合里面插入元素;
(1)插入成功,说明无重复,继续插入;
(2)插入不成功时,元素有重复,记录当前最大长度,查找与当前元素重复的前面重复元素的下标,并清空集合,并从该下标的下一个位置继续插入元素,继续(1)(2)过程,直到遍历到字符串的尾部,返回最大的长度。

leetcode提交超时

#include<iostream>
#include<string>
#include<set>
using namespace std;

int main(){
    string str;
    cin>>str;
    if(str.length() == 0)
        return 0;
    set<char> S;
    int max_len = INT_MIN;
    for(int i=0;i<str.length();){
        if(!S.count(str[i])){
            S.insert(str[i]);
        }else{//插入失败,说明有重复元素,记录当前元素在str中的位置
            int cur_len = S.size();
            max_len = (cur_len > max_len) ? cur_len : max_len;
            for(int j=i-cur_len;j<i;j++){
                if(str[j]==str[i])
                    i=j;//记录下出现重复元素时前面的重复元素对应的下标
            }
            S.clear();//清空set,重新插入元素
            i++;//从当前重复元素的下一个位置开始重新插入set
        }
    }
    cout<<max_len<<endl;
    return 0;
}

第二种方法通过
分别用left和right记录当前遍历过但未出现重复元素的左右下标,如果存在出现重复元素,直接删除重复元素,删除到与当前遍历的元素不重复为止。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.length() == 0)
            return 0;
        set<char> S;
        int left = 0, right = 0, res = 0;
        while(right < s.length()){
            if(!S.count(s[right])){//判断插入是否重复
                S.insert(s[right ++]);
                res = max(res, (int)S.size());
            }else{
                S.erase(s[left++]);//删除重复元素(通过值删除),并记录左下标
            }
        }
        return res;
    }
};