【算法狂想曲】通过滑动窗口找出最长无重复字符的子串长度

2020-03-31   102 次阅读


坠机堡垒都送去三天了还没修好,这几天天天用小电脑在LeetCode上刷题
今天看到了一个题无重复字符的最长子串
题目描述很简单
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

首先看到这题目,就预料到这个题肯定是在时间复杂度上会出问题(废话),所以第一点,肯定不能暴力,暴力秒超时

因此现在就有问题,如何判断当前子串的下一个字符是否存在于当前子串中

之前使用过Java写过一些项目,因此我很快想到了Map,记得C++里面好像也有map,因此我就去网上搜了一下,大体了解具体用法,于是开始撸代码

初次尝试

从字符串开头开始,设立一个扫描索引,相当于扫描字符串中的字符,如果map不包含当前字符,则添加该字符到map中同时最大临时长度++,如果出现过,则将当前最大临时长度与最大长度进行对比,如果更大则更新最大长度,同时清空map,重新定位扫描索引继续扫描

思路非常清晰,代码也很快写出来

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char,int> strChar;                 //定义map
        int MAX=0;                             //最大长度
        int indexA=0;                          //扫描索引
        int start=0;                           //当前子串的开头索引
        int countA=0;                          //最大临时长度
        while(indexA<s.length())              
        {
            if(strChar.find(s[indexA])==strChar.end())  //当当前字符不在map中时
            {
                
                if(strChar.empty())                    //如果Map为空则更新子串开头索引
                start=indexA;		
                countA++;				        //最大临时长度++
                strChar.insert(pair<char,int>(s[indexA],indexA));  //将当前字符插入map
                indexA++;
            }
              //当前字符存在于map中,证明重复
            else{ 
                indexA=start+1;
                strChar.clear();
                if(countA>MAX)
                MAX=countA;
                countA=0;
            }
        }
         if(countA>MAX)           //最后一个字符计数在循环中无法更新,因此在此处更新
                MAX=countA;
        return MAX;
    }
};

然而很遗憾,尝试并没有完全成功
可以说是就差一点,对的,就是一点
986/987

此时我的内心是奔溃的,题目有987组数据,过了986数据。。。
这只能证明最后一组数据太大了不符合常理
说明我尝试的代码的时间复杂度还不足以hold最后一组数据,光看那开头就觉得有内味了

因此我只能打开LeetCode官方题解

改正

官方教程是使用Java书写的,同样给出了三种方法
第一种暴力直接略过
第二种叫做滑动窗口,官方教程使用的是Java中的Set作为数据结构
这个滑动窗口不禁让我想起了计网里的滑动窗口协议
不过咋一看,跟我的代码思路相似,但是有一点不同

  • 我的代码在出现重复字符后直接就把所有字符全部清空了,,并且还得从新的索引开始,显然这里多了很多重复的步骤
  • 而滑动窗口协议,是每次有一个重复字符,就将Set头部(相当于子串头字符)进行删除,删到没有重复字符了,才继续滑动窗口

对比

看到这里,我突然想到了一种情况
考虑字符串abcdefghijklmnopqrstuvwxyQQqjfkxavk

可以看到QQ这里有重复字符
如果用本人之前给定的代码
会出现以下步骤
扫描到子串
abcdefghijklmnopqrstuvwxyQ
下一个字符为Q
显然存在于子串,然后就直接把map中所有内容清空
然后从b开始扫描,一直扫到bcdefghijklmnopqrstuvwxyQ
下一个字符又为Q
存在于子串,然后再次清空map
以此类推循环下去,造成了时间的极大浪费

如果按照滑动窗口的作法话
只需要每次清空开头的字符即可
扫描到子串
abcdefghijklmnopqrstuvwxyQ
下一个为Q重复,将开头字符删除
bcdefghijklmnopqrstuvwxyQ
以此类推,最多只需要经历整个子串长度的时间复杂度即可完成该操作

结果显而易见,本人之前的代码极大地浪费了时间,因此马上进行修正

AC代码

C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char,int> strChar;
        int MAX=0;
        int indexA=0;
        int start=0;         //start仍然为子串开头字符索引
        int countA=0;
        while(indexA<s.length())
        {
            if(strChar.find(s[indexA])==strChar.end())
            {
                countA++;          
                strChar.insert(pair<char,int>(s[indexA],indexA));
                indexA++;
            }
              
            else{
                strChar.erase(s[start++]);      //如果重复,则将子串开头字符从map中删除
                if(countA>MAX)                  
                MAX=countA;               
                countA--;
            }
        }
         if(countA>MAX)
                MAX=countA;
        return MAX;
    }
};

其实还有第三种方法叫做优化的滑动窗口,感兴趣的大佬可以自行了解,这里由于时间问题就不追究了,AC万岁

后来又用Java配合Set写了一遍

Java

class Solution {
    public int lengthOfLongestSubstring(String s) {
Set str1 = new HashSet();
        int left=0;       //定义滑动窗口左部
        int right=0;      //定义滑动窗口右部
        int MAX=0;        //存储最大值
        while(left<s.length() && right<s.length())
        {
            if(!str1.contains(s.charAt(right)))
            {
                str1.add(s.charAt(right));    
                right++;
                 if(right-left>MAX)
                 MAX=right-left;
            }
            else {
        str1.remove(s.charAt(left++));
            }
        }
        return MAX;
    }
}

总结

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议