【每日一题】力扣 3. 无重复字符的最长子串

题目

题目链接：3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 10⁴
• s 由英文字母、数字、符号和空格组成

解题思路

这题我能想到的只有一种思路：暴力

?滑动窗口

虽然说是滑动窗口，但我也要两层循环才行

由于题目要查找的是最长无重复字符子串，所以需要遍历查找该字符串的所有子串才行。遍历子串的方法就是将每个字符作为初始字符向后延长。

延长的意思是向后寻找和当前子串不重复且连续的字符，如果发现重复时，则该子串的长度就可以不用延长了，记录子串的长度并判断是否是最长的子串。

思路很简单，就是有些地方的处理有点麻烦。比如判断向后查找的字符是否是重复字符，这可以用一个数组作为标记解决。对于判断是否是最长的子串，只需要每次取最大值就行（用 max）

对于判断是否是重复字符，官方的题解给的是用 set 容器。在代码上和我写的有点不同，但思路是一样的

代码（C++）

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.size() < 2)
            return s.size();
        int n = s.size(), maxnum = 0;
        for (int i = 0; i < n; i ++ ) {
            string str;
            bool f[260] = {false};
            int j;
            for (j = i; j < n; j ++ ) {
                if (f[s[j]]) {
                    maxnum = max(maxnum, j - i);
                    break;
                }
                f[s[j]] = true;
            }
            if (j == n)
                maxnum = max(maxnum, j - i);
        }
        return maxnum;
    }
};

官方代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int r = 0;
        int maxnum = 0;
        unordered_set<char> set;
        for (int i = 0; i < s.size(); i ++ ) {
            if (i != 0)
                set.erase(s[i - 1]);
            while (r < s.size() && !set.count(s[r])) {
                set.insert(s[r]);
                r ++;
            }
            maxnum = max(maxnum, r - i);
        }
        return maxnum;
    }
};

总结

这题不算难题，思路简单粗暴。如果真要优化什么的，我认为只能在代码的写法和细节上优化，思路应该无法优化了。我只能想到这种思路，如果有更好的思路可以留言。