LeetCode-无重复字符的最长子串（滑动窗口）

LeetCode-无重复字符的最长子串（滑动窗口）

LeetCode-无重复字符的最长子串（滑动窗口）

• • 前言
  • 题目
  • 思路
  • • 1、暴力解法
    • 2、滑动窗口
  • 代码实现

前言

分享一道面试高频算法题——无重复字符的最长子串。作者水平有限，有任何问题欢迎在文章下方留言交流！

关键词：滑动窗口

题目

无重复字符的最长子串

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

示例：

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

力扣原题地址：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

思路 1、暴力解法

凭着我们朴素的想法，可以从第1个字符开始，往后每增加一个字符，判断其是否是无重复字符的，如果含有重复字符，那么就从第2个字符开始，往后每增加一个字符，判断其中是否含有重复字符，以此类推。然后记录最长无重复字符子串的长度。

在判断字符的某一个切片是否含有重复字符时，我们可以定义一个map，从头开始遍历该切片，每遍历一个字符，就在map中查询该字符是否以存在过，如果存在则含有重复子串，如果不存在则将该字符存入map中。

该方法理论上可行，但是时间复杂度很高。套了3层循环，时间复杂度大概是n的3次方，非常高。

2、滑动窗口

上述暴力破解解法中，实际上存在非常多重复的计算。

比如字符串s：”abcdcbcbb“，当我们从第1个字符开始遍历时，我们知道s[0:4]中s[2]和s[4]是重复的，那我们就没有必要再从第2个字符开始遍历了，这是无效计算。

我们可以从第3个字符开始遍历，把第一个重复字符及其前面的字符都从子串中去掉，然后继续往后推进。

这就是滑动窗口的思想。

通俗来讲，滑动窗口其实就是一个队列，比如字符串s：”abcdcbcbb“，进入这个队列（窗口）为 ”abcd“ 满足题目要求，当再进入 ”c“，队列变成了 ”acbdc“，这时候不满足题目要求。所以，我们要移动（滑动）这个队列（窗口）！

我们只要把队列中第一个重复字符及其前面的元素移出就行了，这样便又满足了题目要求，然后继续往后添加元素就行了。期间当有更长无重复字符子串长度，更新最长无重复字符子串的长度。

至于每加入一个字符时，如何判断窗口中是否存在重复字符，只需使用一个map来记录就好了。

代码实现

在此，我用C++实现一下具体代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // len:字符串长度
        int len = s.size();
        // 若字符串为空，则直接返回0
        if(len == 0) return 0;
        // dic:用于记录已出现字符的map<字符，在字符串中的位置>
        unordered_map dic;
        // l:窗口的左边界
        int l = 0;
        // tmp:当前无重复字符子串长度
        int tmp = 0;
        // res:最长无重复字符子串长度
        int res = 0;
        // r:窗口的右边界
        for(int r=0;r					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://www.outofmemory.cn/zaji/5658061.html