LeetCode 热题 100——无重复字符的最长子串(滑动窗口)

题目链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目解析

从s字符串中，去找出连续的子串，使该子串中没有重复字符，返回它的最长长度。

暴力枚举

依次以第一个、第二个、第三个等等为起点去遍历字符串，并且找出不连续子串的最大长度。我们可以借助哈希来解决不重复这个操作。

代码如下

class Solution 
{
public:int lengthOfLongestSubstring(string s) {int n=s.size();int ret = 0;for(int i=0;i<n;i++){// 每次换遍历起点的时候都重新创建一个新的哈希表int hash[128]={0};for(int j=i;j<n;j++){// 将该遍历字符插入哈希表hash[s[j]]++;// 如果该位置字符的次数>1 则存在重复元素 直接跳出if(hash[s[j]]>1)break;// 计算最大长度ret=max(ret,j-i+1);}}return ret;}
};

滑动窗口

暴力枚举的缺点

从我们暴力枚举画图的过程中我们能发现一个事情。如图所示：

注意五角星的位置，我们能发现当我们依次去使用第二个字符为起点的时候，依然是遍历到了此位置，那么是为什么呢？

原因是我们原字符串中的a并没有移走，因此，我们就算以第二个字符作为起点，等到遍历到第二个a的时候依然是重复的，那么我们能不能遍历的时候先把重复的元素给移除掉，然后再进行遍历呢？

那么我们就引出了我们的滑动窗口操作。 

滑动窗口步骤

我们滑动窗口分为几个简单的步骤：

1.定义两个边界的变量 -- left=0,right=0

2.进窗口 -- 让字符进入哈希表
3.判断 -- 窗口内出现重复字符
  出窗口 -- 从哈希表中删除该字符

4.更新结果

图解

代码如下：

class Solution 
{
public:int lengthOfLongestSubstring(string s) {int hash[128]={0};int n=s.size();int ret =0 ;for(int left=0,right=0;right<n;right++){hash[s[right]]++;while(hash[s[right]]>1)hash[s[left++]]--;ret=max(right-left+1,ret);}return ret;}
};