题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个字符串，该字符串由字母、数字、符号和空格组成，求其中无重复字符的最长子串。

思路分享

  • 这是不定长滑动窗口的开题！不过灵神并没有给出模板题解，所以陆爻齐参照着官方题解试着总结一下模板。

  • 哦对，像这种求无重复字符的，如果字符比较特殊，比如本题的字符范围显然就是 ASCII 表，就可以直接用一个长度为 128 的数组记录，相比 unordered_set 方便快捷一点。

  • 先想想暴力，直接两层遍历子串的各种组合，第三层检查是否重复，这过于暴力了。

  • 相比之下，不定长滑动窗口确实高效不少。滑动窗口本质上就可以视为窗口左边和右边的变化，习惯上可以先移动右边，直到再移动窗口内不符合条件，再记录结果（比如本题记录最长的窗口长度即可），接着移动窗口左边，直到窗口内符合条件（这里移动左边不需要单独循环，原因可以看参考代码），再移动窗口右边，重复至尽。

代码解答（强烈建议自行解答后再看）

  • 参考着官方题解写的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0;
        int right = 0; // 虽然是左闭右开，但0开始才能记录所有字母
        int n = s.size();
        vector<int> rec(129, 0);

        for (int i = 0; i < n; i++) {
            if (i!=0) {
                rec[s[i-1]]--;
            }
            while(right < n && rec[s[right]]==0) {
                rec[s[right]]++;
                right++;
            }
            ans = max(ans, right-i);
        }

        return ans;
    }
};