查看“Sliding window”的源代码

使用左右两个指针，按一定规则向右移动。注意 window 的大小并不一定是固定的。

== 使用 pattern ==
<ref>[http://www.noteanddata.com/leetcode-3-Longest-Substring-Without-Repeating-Characters-java-sliding-windows-solution-note.html#sliding-windows滑动窗口的特征和基本模版 sliding windows 滑动窗口的特征和基本模版]</ref> <ref>https://blog.csdn.net/fuxuemingzhu/article/details/82931106</ref>

在需要找一个区间的问题中，

'''第一种情况：'''首先移动右指针使得满足要求，再移动左指针直到不满足要求，再移动右指针，持续如此，直到区间的右边界到达整体的结束点。
<syntaxhighlight lang=python>
left = 0
init state
ret = worse case retval
for right in range(n):
    update state
    while state is valid:
        sol = f(left, right)
        if sol is better than ret:
            ret = sol
        left += 1
        update state
return ret
</syntaxhighlight>

'''第二种情况：'''首先移动右指针直到不满足要求，再移动左指针直到满足要求，此时记录当前状态，若更优则记录下来。持续如此，直到区间的右边界到达整体的结束点。
<syntaxhighlight lang=python>
left = 0
init state
ret = worse case retval
for right in range(n):
    update state
    while state is not valid:
        left += 1
        update state
    sol = f(left, right)
    if sol is better than ret:
        ret = sol
return ret
</syntaxhighlight>

== 相关题目 ==

=== [https://leetcode.com/problems/minimum-window-substring/ LeetCode 76. Minimum Window Substring] ===

第一种情况。Python 解法：

<syntaxhighlight lang=python>
def minWindow(self, s: str, t: str) -> str:
    ret = ''
    # cnt: how many chars of t has been covered. just for speeding up the algo
    cnt = 0
    left = 0
    min_size = float('inf')
    chars = Counter()
    target = Counter(t)
                                                                               
    for right, sc in enumerate(s):
        # for a new right pointer, update the state
        chars[sc] += 1
        if chars[sc] <= target[sc]:
            cnt += 1
        # move the left pointer right until the state becomes invalid
        while cnt == len(t):
            if (size := right - left + 1) < min_size:
                min_size = size
                ret = s[left:right + 1]
            # for a new left pointer, update the state
            sl = s[left]
            left += 1
            chars[sl] -= 1
            if chars[sl] < target[sl]:
                cnt -= 1
    return ret
</syntaxhighlight>

=== LeetCode 340. Longest Substring with At Most K Distinct Characters ===

第二种情况。Python 解法：

<syntaxhighlight lang=python>
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
    left = 0
    ret = 0
    distinct = 0
    chars = Counter()
    for right, ch in enumerate(s):
        # move the right pointer until the state is invalid
        if chars[ch] == 0:
            distinct += 1
        chars[ch] += 1
        while distinct > k and left <= right:
            # move the left pointer until the state is valid
            c = s[left]
            left += 1
            chars[c] -= 1
            if chars[c] == 0:
                distinct -= 1
        # after the state becomes valid, record the best result
        ret = max(right - left + 1, ret)
    return ret
</syntaxhighlight>

== 参考资料 ==

<references />

[[Category:刷题]]
[[Category:双指针‎]]