3. 无重复字符的最长子串(C++)

题目英文描述:
Given a string, find the length of the longest substring without repeating characters.

题目中文描述:
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

思路:利用hashmap(不用hashset是为了记录下标,减少循环次数),利用滑动窗口去寻找不含重复字符的最长字串

代码:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> hash;
        int l = 0, len = 0, ans = 0;
        for(int r = 0; r < s.size(); ++r) {
            if(hash.find(s[r]) != hash.end() && hash[s[r]] >= l) { 
                //等于end()是没有, 最后一个条件是为了保证在子串中查找字符是否重复,如“abba”
                //等号是子串头尾字符相等,如“pwwkew”,当r在末尾时,l=‘w’
                l = hash[s[r]] + 1;
                len = r - l;       //计算新子串长度,两条语句顺序不能变
            }
            hash[s[r]] = r;
            ++len;
            ans = max(ans, len);
        }
        return ans;
    }
};
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容