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。
上图我们可以看出,随着窗口在数组上向右移动,窗口内的数据也在不断变化,我们只用对窗口内连续区间内的数据进行处理即可。由于区间是连续的,因此当窗口移动时只用对旧窗口的数据进行裁剪处理,这样便减少了重复计算,降低了时间复杂度。
以上图为例,当窗口位于[1,3,5]时,处理完该窗口的数据之后,将窗口向右移动一格,等于是将原有窗口左边的1裁剪掉,然后将窗口右边的6添加上,而整个过程看起来就像窗口在向右移动一样。
对于类似“请找到满足 xx 的最 x 的区间(子串、子数组)的 xx ”这类问题都可以使用该方法进行解决。
需要注意的是:窗口的移动是按照移动的顺序来进行的;窗口的大小不一定是固定的,可以不断缩小或变大的。
对于滑动窗口算法的基本解题思路,以字符串S示例如下:
其中,第2步相当于在寻找一个「可行解」,然后第3步在优化这个「可行解」,最终找到最优解。左右指针轮流前进,窗口大小增增减减,窗口不断向右滑动。
学习了窗口滑动之后,我们回到LeetCode的题目上,是将上述示例的固定窗口变为了变化大小的窗口,而将求和换成了判断是否包含指定字符。
因此,套用上面的思路来进行分析。以字符串“dvdf”为例,通过下图来演示滑动的过程。
在上述流程中,可分解为以下步骤:
理解了上述步骤,我们再来看原题的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:面试关:如何找出字符串中无重复最长子串?》