字符串系列之滑动窗口

大家好，滑动窗口算法一般是作用在字符串或者数组上，通过不断的滑动逻辑窗口，在特定窗口大小内进行计算的过程。滑动窗口的方式可以降低时间复杂度，从而减短计算的执行时间。

比如说在字符串s="5189623196"?中，窗口大小?w=5，找出每个窗口字符子串的和。

普通的计算方式：每 5 个进行一次求个计算，时间复杂度方面能够达到?O(N^2)。

利用窗口的方式：可很大程度可以减小时间方面的消耗。就拿引例来说，时间复杂度应该是O(N)的线性复杂度。

其核心思路是：窗口在每一次的滑动前后，中间元素内容没有改变，仅仅改变的是开头和结尾元素，即：下一窗口内元素之和 = 上一窗口元素和 - 离开窗口元素值 + 新加入窗口元素值。

下面分步骤进行讨论，将最终结果写入到?res?中。

步骤一：直接计算窗口内元素和，res = [29]

步骤二：在上一步骤的基础上，减去离开窗口的元素，加上新加入窗口的元素。

步骤三：继续在上一步骤的基础上，减去离开窗口的元素，加上新加入窗口的元素

相同逻辑继续执行....

步骤六：滑动窗口将最后一个元素包含进来

上述每一步骤中，将?sum?值都添加到最终的结果变量?res?中。滑动窗口这样的思维方式就很巧妙的进行在窗口的不断移动，进而产生各元素在窗口边界进进出出，利用这一点，在时间复杂度方面进行了一个很大提升。

Python代码如下：

class Solution(object):
    def sumSlidingWindow(self, s, w):
        sum = 0
        res = []
        # 计算第一个窗口数字之和
        for item in range(5):
            sum += s[item]
        res.append(sum)
        # 后面利用滑动窗口思想进行计算
        for item in range(w, len(s)):
            sum -= s[item-w]
            sum += s[item]
            res.append(sum)
        return res

下面用两个?LeetCode 经典案例进一步阐述滑动窗口这类题目。

1.字符串的排列

给两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

输入：s1 =?"ab"?s2?=?"eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一?("ba").

首先，两个字符串的排列，首先可以想到字典，根据字典去比较。词典可根据两个不同字符串将给到的字符进行计数，因此，这样很同容易进行比较。

另外，在遍历?s2?的时候，使用滑动窗口，该窗口的长度是字符串?s1?的长度，遍历?s2?使得字符不断的出入，在此过程中比较两个字典。

整个过程，记?s1?的长度为?size1，s2?的长度为?size2，窗口大小为?size1，不断遍历?s2，直到?s2?的结尾。

记??s1?的字典为?dict_s1，记s1的字典为dict_s2，在遍历s2的过程中，每滑动一次窗口，比较?dict_s1?和?dict_s2?是否相等。

窗口滑动过程中，需要删除滑出窗口的元素以及新增滑入窗口的元素。

删除滑出窗口的元素：广义上是从字典?dict_s2?中删除，注意此处不能直接删除，因为可能会有重复元素存在，比如：{'a':2}，所以只能是将 value 值减 1。之后再判断 value 值为否为 0，如果为 0 了，这个时候就可以直接将该元素从字典中删除。

新增滑入窗口的元素：直接将滑入窗口的元素添加进字典中。

下面用几个图清晰的一步一步操作：

初始化?s1?对应的字典?dict_s1={'a':1,'b':1}

①?s2?对应的字典为图中窗口中的元素?dict_s2={'e':1,'i':1}。

最后判断?dict_s1 != dict_s2

② 向右滑动窗口，由于元素e的 value 值为 1，直接删除该元素，加入新元素d，此时，dict_s2={'i':1,'d':1}。

最后判断?dict_s1 != dict_s2

③ 继续向右滑动窗口，由于元素?i?的 value 值为 1，直接删除该元素，加入新元素?b，此时，dict_s2={'d':1,'b':1}。

最后判断?dict_s1 != dict_s2

③ 继续向右滑动窗口，由于元素?d?的 value 值为 1，直接删除该元素，加入新元素?a，此时，dict_s2={'b':1,'a':1}。

最后判断?dict_s1 == dict_s2，此时可以直接返回?True。不用在继续窗口滑动了。

这个题虽然在 LeetCode 中标记为中等，但是用滑动窗口的方式去解决还是非常容易理解的。

下面是 Python 代码的实现：

class?Solution(object):
????def?checkInclusion(self,?s1,?s2):
????????size1?=?len(s1)
????????size2?=?len(s2)
????????if?size1?>?size2:
????????????return?False

????????dict_s1?=?collections.Counter(s1)
????????dict_s2?=?collections.Counter(s2[:size1-1])
????????left?=?0
????????for?right?in?range(size1-1,?size2):
????????????#?增加新添加的元素
????????????dict_s2[s2[right]]?+=?1
????????????#?判断如果字典相同，则返回?True
????????????if?dict_s1?==?dict_s2:
????????????????return?True
????????????#?删除左边剔除的元素(首先需要将左边元素的?value?值减?1)
????????????dict_s2[s2[left]]?-=?1
????????????#?value?值为?0?的时候，就可以删除该元素了
????????????if?dict_s2[s2[left]]?==?0:
????????????????del(dict_s2[s2[left]])
????????????#?窗口整体向右移动一格
????????????left?+=?1
????????????right?+=?1
????????return?False

2.无重复字符的最长子串

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

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

想要判断字符是否存在，通常会使用到字典结构来判断是否存在。

首先，初始化窗口左右端?left=0?和?right=0，初始化字典?words?用来存放已加入字符的元素（key）和元素下标（value），例如，words={'a':0,'b':1,'c':2}

然后，right?指针向右移动，判断新加入元素是否存在于字典中，如果存在，让窗口左边界指向字典对应 value 值的下一个位置，并且更新字典中对应元素的下标值（value）；如果不存在，则加入字典?words中；

注意点：

中间有可能 left 已经更新到后边，而新判断的元素可能在前面，会导致 left 变小，所以需要采用 max 来进行判断

举例：abba，执行到第二个 b 的时候，left=2，此时words={'a':0,'b':2}。后面再判断最后的 a 的时候，就会使得 left=0+1=1

因此，需要 left = max(words.get(v) + 1, left)

每一步骤记录最长子串长度，依旧用几个图清晰的一步一步操作：

① left=0, right=0, 加入新元素?'a'，words={'a':0}, 窗口长度为1。

② left=0, right=1, 加入新元素?'b'，words={'a':0, 'b':1}, 窗口长度为2。

③ left=0, right=2, 加入新元素?'c'，words={'a':0, 'b':1, 'c':2}, 窗口长度为3。

④ left=0, right=3, 加入新元素?'a';

发现?a?已经在 words={'a':0, 'b':1, 'c':2} 存在；

则更新 left=max(words.get('a') + 1, left)=1，words={'a':3, 'b':1, 'c':2}，窗口长度为3。

⑤ left=1, right=4, 加入新元素?'b';

发现?'b'?已经在 words={'a':3, 'b':1, 'c':2} 存在；

则更新 left=max(words.get('b') + 1, left)=2，words={'a':3, 'b':4, 'c':2}，窗口长度为3。

⑥ left=2, right=5, 加入新元素?'c';

发现?'c'?已经在 words={'a':3, 'b':4, 'c':2} 存在；

则更新 left=max(words.get('c') + 1, left)=3，words={'a':3, 'b':4, 'c':5}，窗口长度为3。

⑦ left=3, right=6, 加入新元素?'b';

发现?b?已经在 words={'a':3, 'b':4, 'c':5} 存在；

则更新 left=max(words.get('b') + 1, left)=5，words={'a':3, 'b':6, 'c':5}，窗口长度为2。

⑧ left=5, right=7, 加入新元素?'b';

发现?'b'?已经在 words={'a':3, 'b':6, 'c':5} 存在；

则更新 left=max(words.get('b') + 1, left)=7，words={'a':3, 'b':7, 'c':5}，窗口长度为1。

根据每一步骤记录的窗口长度，可得到最长窗口为 3。下面就由上述逻辑得到最终的代码：

class?Solution(object):
????def?lengthOfLongestSubstring(self,?s):
????????if?not?s:
????????????return?0
????????left,?right?=?0,?0
????????length?=?1
????????words?=?{}
????????for?right,?v?in?enumerate(s):
????????????if?s[right]?in?words.keys():
????????????????print(words.get(v)?+?1,?left)
????????????????left?=?max(words.get(v)?+?1,?left)
????????????length?=?max(right-left+1,?length)
????????????#?将当前值的?value?值覆盖
????????????words[v]?=?right
????????print(words)
????????return?length

综上所述，本文字符串系列有关滑动窗口的介绍已经完成，关于其他滑动窗口问题以后会继续总结。