滑动窗口思维--挑战“无重复字符的最长子串”

 

 

文章来源： 饭饭的Python学习之路

作者： 一粒米饭

 

今天要挑战的是“无重复字符的最长子串”。

难度：中等

题目描述：

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

示例1:

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

示例2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
   
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

题目原始链接

解题思路：

这道题的解题思路主要是利用滑动窗口思维。

什么是滑动窗口

滑动窗口作为双指针算法的一种特殊形式，在日常算法中尤其是字符串匹配查询中经常用到。

其基本思想是通过使用特定大小的子列表，在遍历完整列表的同时进行特定的操作，以达到降低了循环的嵌套深度。

滑动窗口的基本逻辑如下：

1. 使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。
2. 先不断地增加 right 指针扩大窗口 [left, right]，直到窗口符合要求
3. 停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求。同时，每次增加 left，我们都要更新一轮结果。
4. 重复第 2 和第 3 步，直到 right 到达尽头。

代码实现：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        w = ""
        l = 0
        max_l = 0
        for c in s:
            if c in w:
                left = w.index(c) + 1
                w = w[left:]
                l -= left
            w += c
            l += 1
            if l > max_l:
                max_l = l
        return max_l

结果:

除了无重复字符的最长子串，滑动窗口还可以用来解决连续子数组的最大和、和为特定值的连续正整数序列、长度最小的子数组等问题。