Leetcode刷题笔记题解(C++):无重复字符的最长子串

2024-01-07 22:43:37

思路:

利用滑动窗口的思想,用起始位置startindex和curlength来记录这个滑动窗口的大小,并且得出最长距离;利用哈希表来判断在滑动窗口中是否存在重复字符,代码如下所示:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //如果为空字符串,则返回0
        if(s.length() == 0) return 0;
        int maxlength = 0;//定义最长的字符串的长度
        int curlenth =0;//定义当前的不重复的字符串长度
        int startindex = 0;//滑动窗口的起始位置
        unordered_map<char,int>hashtable;
        for(int i = 0;i<s.length();i++){
            //如果当前字符之前不存在则加入hash表中,字符串长度+1
            if(hashtable.find(s[i]) == hashtable.end()){
                curlenth++;
                hashtable[s[i]] = i;//加入hash表
            }
            //如果当前字符在hash表中已经存在
            else{
                //取一下当前最大字符串的长度
                if(curlenth > maxlength) maxlength = curlenth;
                //更新滑动窗口的位置
                startindex = max(hashtable[s[i]],startindex);
                //当前的长度就为两个重复字符之间的长度
                //比如abcabcd   i=3 startindex=0 curlength=3
                curlenth = i - startindex;
                //更新重复字符最新出现的位置
                hashtable[s[i]] = i;
            }
        }
        //最后比较一下最后这个最长的字符串长度和上一个最大字符串的长度
        if(curlenth > maxlength) maxlength = curlenth;
        return maxlength;
    }
};

文章来源:https://blog.csdn.net/qq_27524749/article/details/135424204
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。