【每日一题】LeetCode每日一题-无重复字符的最长子串

题目链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

题目描述：

给定一个字符串 s，找到其中不包含重复字符的最长子串的长度。

示例 1:

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

示例 2:

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

示例 3:

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

引言

这道题有两种做法:

• 简单粗暴的暴力枚举
• 优雅的滑动窗口

解决方法

暴力枚举方式

暴力枚举方式顾名思义，我一个个去比较，使用两重循环，外层循环每执行一次，我内层循环去检查是否满足条件，如果满足的话就则继续往后推，直到不满足时返回数据。
这种方式唯一的有点我估计就是简单了，大部分人的第一个想法应该就是这个，实现起来也很简单但是时间复杂度会比较高，因为使用了for嵌套所以复杂度是O(N^2)，代码如下：

class Solution {
public:int lengthOfLongestSubstring(const string& s) {int max_len = 0; // 使用更具语义化的变量名for (int i = 0; i < s.length(); ++i) {int t = getSubstringLength(s, i);max_len = std::max(max_len, t); // 使用 std::max}cout << max_len << endl;return max_len;}private:static int getSubstringLength(const string& s, int index) {int t = 0;unordered_set<char> seen; // 使用 unordered_set 简化for (int i = index; i < s.length(); ++i) {char c = s[i];if (seen.find(c) == seen.end()) {t++;seen.insert(c);} else {return t;}}return t;}
};

滑动窗口

滑动窗口相比暴力方式时间复杂度更低(O(N))，空间复杂度是O(N)。

如果你不知道什么是滑动窗口，以及不了解其底层原理可以看完另外一篇博客，其中有对本地的详解：

• 【数据结构】滑动窗口算法详解：高效解决子串问题

具体代码如下：

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;int lengthOfLongestSubstring(const string& s) {int max_length = 0; // 最长子串长度unordered_set<char> char_set; // 用于记录出现的字符// 外循环控制右边界for (int left = 0, right = 0; right < s.length(); ++right) {// 收缩左边界，直到当前字符不再出现while (char_set.find(s[right]) != char_set.end()) {char_set.erase(s[left++]);}char_set.insert(s[right]); // 插入当前字符max_length = max(max_length, right - left + 1); // 更新最大长度}cout << "最长无重复子串的长度为: " << max_length << endl;return max_length;
}