一.题目描述
无重复字符的最长子串
二.思路分析
题目要求我们找符合要求的最长子串，要求是不能包含重复字符
确定一个子串只需确定它的左右区间即可，于是我们可以两层循环暴力枚举所有的子串，找到符合要求的，并通过比较得到最长的长度。还有一个问题，怎么确定有没有重复字符呢？可以使用哈希表,如果把字符丢进哈希表后没有重复，那么right继续向后枚举，如果重复了直接退出循环，后面的不用枚举了，肯定也会重复。
class Solution {
public:
int lengthOfLongestSubstring(string s)
{
int n = s.size();
int ret = 0;
for (int left = 0; left < n; left++)
{
int hash[128] = {0};
for (int right = left; right < n; right++)
{
int in = s[right];
hash[in]++;
if (hash[in] > 1)//出现重复的字符了
{
break;
}
//没有出现重复字符
ret = max(ret, right - left + 1);
}
}
return ret;
}
};两层for循环，时间复杂度是O(n^2)，leetcode上面不会超时能通过。但用暴力枚举太浪费这道题了，可以使用滑动窗口优化。
要想使用滑动窗口必须证明left和right都只会向前移动。
left固定在第一个位置，right不断向后移动，移动过程中，如果没有出现重复字符则不断更新结果。当right移动到如图所示位置时，出现了重复字符，故left位置已经枚举完毕。
按照暴力枚举方法，left向前移动一步，right回退到left位置。但是最终right还是会走到原先标记的位置。因为经过上一轮枚举，[left - 1, tmp)区间内都是没有重复字符的，所以right会一直往前走。
所以right不必退回来，保持在原地不动，让left向右移动即可。我们发现此时区间内没有重复元素了，所以要更新结果，right继续向后移动。接下来的步骤就和前面的一样了。但是这里的left向后移动一步刚好就跳过了那个重复的元素，接下来我们看一个不一样的例子
这里区间内出现重复元素，left向后移动一步
但此时还是有重复元素，此时right也没有必要向后枚举了，因为肯定也是重复的。所以left还要继续向后移动，直到跳过重复的字符w，right才能被解放，继续向后移动。故left可能向后移动多步，这是一个循环的过程。
三.代码编写
根据滑动窗口的代码模版，我们只需确定以上几个具体的步骤。那么什么时候更新结果呢？当我们找到符合要求的子串是就更新,什么时候是符合要求的呢？
当判断条件不成立
或者判断条件成立，但通过不断地出窗口，最终使判断条件不成立时是符合要求的。所以更新结果应该放在整个循环的最后。文章来源：https://www.toymoban.com/news/detail-679926.html
class Solution {
public:
int lengthOfLongestSubstring(string s)
{
int n = s.size();
int ret = 0;
int hash[128] = {0};
int left = 0, right = 0;
while (right < n)
{
//进窗口
int in = s[right];
hash[in]++;
//判断
while (hash[in] > 1)
{
//出窗口
int out = s[left];
hash[out]--;
left++;
}
//更新结果
ret = max(ret, right - left + 1);
right++;
}
return ret;
}
};时间复杂度O(n),效率大大提升文章来源地址https://www.toymoban.com/news/detail-679926.html
到了这里，关于【滑动窗口】leetcode3:无重复字符的最长子串的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
