LeetCode 03：面试关：如何找出字符串中无重复最长子串？

客官°小女子只卖身不卖艺 2023-01-11 08:29 14阅读 0赞

LeetCode第3题，“无重复字符的最长子串”，曾经面试的过程中遇到过的一道算法题。通过这道题，我们能够学到算法中一个比较常见的解题方法：滑动窗口算法。

由于LeetCode中很多题都是基于“滑动窗口算法”进行解答，因此本篇文章将重点放在“滑动窗口”上，而不仅仅是这道算法题。当理解了滑动窗口的基本原理之后，所有类似的题都可以轻易解答。

下面来看具体的题目和解题方法。

### “无重复字符的最长子串” ###

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

**题目描述**：

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

**示例**：

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

### 题目说明 ###

题目很简单，就是从一个字符串中找出不包含重复字符的最长子串的长度。

该题如果用暴利破解的方法进行循环判断，则时间复杂度直接变为O(n^2)，是比较恐怖的。因此，可采取滑动窗口的方法来降低时间复杂度。

### 什么是滑动窗口？ ###

滑动窗口算法是在一个特定大小的字符串或数组上进行操作，而不在整个字符串和数组上操作，这就降低了问题的复杂度，从而也降低了循环的嵌套深度。滑动窗口主要应用在数组和字符串的场景。

#### 简单示例 ####

先通过一个简单的示例来看一下滑动窗口的运作，比如有一个数组\[1,3,5,6,2,2\]，设定滑动窗口（window）大小为3，那么当窗口从数组开始位置滑动到最终位置时依次计算每个窗口内3个元素的和，表示为sum。

![image][]

上图我们可以看出，随着窗口在数组上向右移动，窗口内的数据也在不断变化，我们只用对窗口内连续区间内的数据进行处理即可。由于区间是连续的，因此当窗口移动时只用对旧窗口的数据进行裁剪处理，这样便减少了重复计算，降低了时间复杂度。

以上图为例，当窗口位于\[1,3,5\]时，处理完该窗口的数据之后，将窗口向右移动一格，等于是将原有窗口左边的1裁剪掉，然后将窗口右边的6添加上，而整个过程看起来就像窗口在向右移动一样。

对于类似“请找到满足 xx 的最 x 的区间（子串、子数组）的 xx ”这类问题都可以使用该方法进行解决。

#### 滑动窗口的基本步骤 ####

需要注意的是：窗口的移动是按照移动的顺序来进行的；窗口的大小不一定是固定的，可以不断缩小或变大的。

对于滑动窗口算法的基本解题思路，以字符串S示例如下：

*  （1）采用双指针来指定窗口的范围，初始化left=right=0，而索引闭区间\[left,right\]便是一个窗口。
 *  （2）不断增大窗口的right指针，直到窗口中的字符串满足条件。
 *  （3）此时，停止right的增加，转而不断增加left指针，用于缩小窗口\[left,right\]，直到窗口中的字符串不再符合要求。每增加一次left，需要更新一轮结果。
 *  （4）重复第2和第3步，直到right到达字符串的尽头。

其中，第2步相当于在寻找一个「可行解」，然后第3步在优化这个「可行解」，最终找到最优解。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。

### 解题 ###

学习了窗口滑动之后，我们回到LeetCode的题目上，是将上述示例的固定窗口变为了变化大小的窗口，而将求和换成了判断是否包含指定字符。

因此，套用上面的思路来进行分析。以字符串“dvdf”为例，通过下图来演示滑动的过程。  
![在这里插入图片描述][277f2fdcf94967f6a75c7c856a3939ca.png_pic_center]

在上述流程中，可分解为以下步骤：

*  （1）选定初始值left=right=0，也就是窗口\[0,0\]。
 *  （2）判断right右边字符在窗口内是否已经存在；
 *  （3）发现字符v在窗口中没有，则可right右移一位，窗口变为\[0,1\]；
 *  （4）继续扩展右边界，right=2，发现d已经存在于窗口当中，则停止继续右移；
 *  （5）此时窗口的长度便是以d开通的子串的长度，比较当前窗口长度和历史max（默认值0）大小，发现2>0，于是更新max为2。
 *  （6）开始移动left，窗口变为\[1,1\]；
 *  （7）继续扩展右边界，发现d不存在于窗口当中，此时窗口变为\[1,2\]；
 *  （8）继续扩展右边界，发现f不存在于窗口当中，此时窗口变为\[1,3\]；
 *  （9）到达字符串的最大长度，停止右移，此时比较当前窗口长度和历史max大小，发现3>2，于是更新max为3。
 *  （10）得出，不包含重复字符的最长子串的长度3。

理解了上述步骤，我们再来看原题的Java代码实现：

class Solution {
        public int lengthOfLongestSubstring(String s) {
            int n = s.length();
            int k = 0, max = 0;
            Set<Character> set = new HashSet<>();
            for(int i=0; i< n; i++){
                if(i != 0){
                    set.remove(s.charAt(i-1));
                }
    
                while(k < n && !set.contains(s.charAt(k))){
                    set.add(s.charAt(k));
                    k++;
                }
                max = Math.max(max,set.size());
            }
            return max;
        }
    }

上述代码中for循环中的i相当于left，k相当于right，而max是存储历史最长字符串的值。而窗口内的字符通过Set<Character>来存储，判重通过Set的contains方法，获取最大值通过Math的max方法来操作。

最后，此算法的时间复杂度为O(n)，其中n是字符串的长度。左指针和右指针分别会遍历整个字符串一次。

### 小结 ###

本篇文章我们重点学习的应该是滑动窗口的原理及步骤，当掌握了滑动窗口的知识之后，LeetCode的题只不过是对滑动窗口的一个示例而已。对于算法题，千万不要死记硬背解题代码。

原文链接：《[LeetCode 03：面试关：如何找出字符串中无重复最长子串？][LeetCode 03]》

--------------------

**程序新视界**  
公众号“ **程序新视界**”，一个让你软实力、硬技术同步提升的平台，提供海量资料

![微信公众号：程序新视界][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvNTQxMDc1NzU0_size_16_color_FFFFFF_t_70_pic_center]

[image]: /images/20221119/a6c4569532874140942b03e139188f93.png
[277f2fdcf94967f6a75c7c856a3939ca.png_pic_center]: https://img-blog.csdnimg.cn/img_convert/277f2fdcf94967f6a75c7c856a3939ca.png#pic_center
[LeetCode 03]: https://mp.weixin.qq.com/s/rBygioZXYCGgsAW_nc6tOA
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvNTQxMDc1NzU0_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200326082919289.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvNTQxMDc1NzU0,size_16,color_FFFFFF,t_70#pic_center