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

滑动窗口

设置滑动窗口， $l$ 维护左窗口 ， $r$ 维护右窗口 ，利用哈希表统计字母出现次数。

1. 遍历字符串 $s$ ，$l$ 循环右移，每次移动 ， $l$ 指向的字母 $s[l]$ 出现次数++ 。
2. 如果窗口内 $s[l]$ 出现次数大于 $1$ ， $r$ 循环右移 ， 每次移动， $r$ 指向的字母 $s[r]$ 出现次数- - 。 当 $s[l]$ 出现次数等于 $1$ 时 ， 回到操作 $1.$

上述操作保证窗口内每个字母最多出现一次 ， 符合题意——无重复字符的子串。其中最长子串的长度，即为所求。

代码展示

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<int,int> mp;
        int l = 0;
        int ans = 0;
        for(int r = 0;r<s.size();r++){
            mp[s[r]]++;
            while(mp[s[r]]>1) mp[s[l++]]--;
            ans = max(ans,r-l+1);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC

复杂度分析

1. 时间复杂度: $O(n)$， $n$ 是 $s$ 的长度 。 一次遍历 $s$ ，左右指针分别最多右移 $O(n)$ 次 ， 总时间复杂度 $O(2n)$ ， 忽略常数时间复杂度 $O(n)$ 。
2. 空间复杂度: $O(|C|)$，哈希表的空间复杂度 $O(|C|)$ ， $|C|=128$ ， 对应 $128$ 个 $ASCII$ 字符 。