友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

微信

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

Sliding Window 滑动窗口

滑动窗口类型的题目经常是用来执行数组或是链表上某个区间（窗口）上的操作。比如找最长的全为1的子数组长度。滑动窗口一般从第一个元素开始，一直往右边一个一个元素挪动。当然了，根据题目要求，我们可能有固定窗口大小的情况，也有窗口的大小变化的情况。

下面是一些我们用来判断我们可能需要上滑动窗口策略的方法：

  • 这个问题的输入是一些线性结构：比如链表呀，数组啊，字符串啊之类的

  • 让你去求最长/最短子字符串或是某些特定的长度要求

经典题目

  1. 3. 无重复字符的最长子串

  2. 30. 串联所有单词的子串

  3. 76. 最小覆盖子串

  4. [0159-longest-substring-with-at-most-two-distinct-characters]

  5. [0187-repeated-dna-sequences]

  6. 209. 长度最小的子数组

  7. [0219-contains-duplicate-ii]

  8. [0220-contains-duplicate-iii]

  9. 239. Sliding Window Maximum

  10. [0340-longest-substring-with-at-most-k-distinct-characters]

  11. 395. Longest Substring with At Least K Repeating Characters

  12. [0413-arithmetic-slices]

  13. [0424-longest-repeating-character-replacement]

  14. 438. Find All Anagrams in a String

  15. 480. Sliding Window Median

  16. [0487-max-consecutive-ones-ii]

  17. 567. Permutation in String

  18. [0594-longest-harmonious-subsequence]

  19. [0632-smallest-range-covering-elements-from-k-lists]

  20. [0643-maximum-average-subarray-i]

  21. [0658-find-k-closest-elements]

  22. [0683-k-empty-slots]

  23. [0689-maximum-sum-of-3-non-overlapping-subarrays]

  24. 713. Subarray Product Less Than K

  25. 718. 最长重复子数组

  26. [0727-minimum-window-subsequence]

  27. [0837-new-21-game]

  28. [0862-shortest-subarray-with-sum-at-least-k]

  29. 904. Fruit Into Baskets

  30. [0930-binary-subarrays-with-sum]

  31. [0978-longest-turbulent-subarray]

  32. 992. Subarrays with K Different Integers

  33. [0995-minimum-number-of-k-consecutive-bit-flips]

  34. [1004-max-consecutive-ones-iii]

  35. [1031-maximum-sum-of-two-non-overlapping-subarrays]

  36. [1044-longest-duplicate-substring]

  37. [1052-grumpy-bookstore-owner]

  38. [1100-find-k-length-substrings-with-no-repeated-characters]

  39. [1151-minimum-swaps-to-group-all-1s-together]

  40. [1156-swap-for-longest-repeated-character-substring]

  41. [1176-diet-plan-performance]

  42. [1208-get-equal-substrings-within-budget]

  43. [1234-replace-the-substring-for-balanced-string]

  44. [1248-count-number-of-nice-subarrays]

  45. [1297-maximum-number-of-occurrences-of-a-substring]

  46. [1343-number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold]

  47. [1358-number-of-substrings-containing-all-three-characters]

  48. [1423-maximum-points-you-can-obtain-from-cards]

  49. [1425-constrained-subsequence-sum]

  50. [1438-longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit]

  51. [1456-maximum-number-of-vowels-in-a-substring-of-given-length]

  52. [1477-find-two-non-overlapping-sub-arrays-each-with-target-sum]

  53. [1493-longest-subarray-of-1s-after-deleting-one-element]

  54. [1499-max-value-of-equation]

  55. [1610-maximum-number-of-visible-points]

  56. [1652-defuse-the-bomb]

  57. [1658-minimum-operations-to-reduce-x-to-zero]

  58. [1695-maximum-erasure-value]

  59. [1703-minimum-adjacent-swaps-for-k-consecutive-ones]

  60. [1763-longest-nice-substring]

  61. [1838-frequency-of-the-most-frequent-element]

  62. [1839-longest-substring-of-all-vowels-in-order]

  63. [1852-distinct-numbers-in-each-subarray]

  64. [1871-jump-game-vii]

  65. [1876-substrings-of-size-three-with-distinct-characters]

  66. [1888-minimum-number-of-flips-to-make-the-binary-string-alternating]

  67. [1918-kth-smallest-subarray-sum]

  68. [1984-minimum-difference-between-highest-and-lowest-of-k-scores]

  69. [2009-minimum-number-of-operations-to-make-array-continuous]

  70. [2024-maximize-the-confusion-of-an-exam]

  71. [2067-number-of-equal-count-substrings]

  72. [2090-k-radius-subarray-averages]

  73. [2106-maximum-fruits-harvested-after-at-most-k-steps]

  74. [2107-number-of-unique-flavors-after-sharing-k-candies]

  75. [2134-minimum-swaps-to-group-all-1s-together-ii]

  76. [2156-find-substring-with-given-hash-value]

  77. [2260-minimum-consecutive-cards-to-pick-up]

  78. [2269-find-the-k-beauty-of-a-number]

  79. [2271-maximum-white-tiles-covered-by-a-carpet]

  80. [2302-count-subarrays-with-score-less-than-k]

  81. [2379-minimum-recolors-to-get-k-consecutive-black-blocks]

  82. [2398-maximum-number-of-robots-within-budget]

  83. [2401-longest-nice-subarray]

  84. [2411-smallest-subarrays-with-maximum-bitwise-or]

  85. [2444-count-subarrays-with-fixed-bounds]

  86. [2461-maximum-sum-of-distinct-subarrays-with-length-k]

  87. [2516-take-k-of-each-character-from-left-and-right]

  88. [2524-maximum-frequency-score-of-a-subarray]

  89. [2528-maximize-the-minimum-powered-city]

  90. [2537-count-the-number-of-good-subarrays]

  91. [2555-maximize-win-from-two-segments]

  92. [2653-sliding-subarray-beauty]

  93. [2730-find-the-longest-semi-repetitive-substring]

  94. [2743-count-substrings-without-repeating-character]

  95. [2747-count-zero-request-servers]

  96. [2760-longest-even-odd-subarray-with-threshold]

  97. [2762-continuous-subarrays]

  98. [2779-maximum-beauty-of-an-array-after-applying-operation]

  99. [2781-length-of-the-longest-valid-substring]

  100. [2799-count-complete-subarrays-in-an-array]

  101. [2831-find-the-longest-equal-subarray]

  102. [2841-maximum-sum-of-almost-unique-subarray]

  103. [2875-minimum-size-subarray-in-infinite-array]

  104. [2902-count-of-sub-multisets-with-bounded-sum]

  105. [2904-shortest-and-lexicographically-smallest-beautiful-string]

  106. [2932-maximum-strong-pair-xor-i]

  107. [2935-maximum-strong-pair-xor-ii]

  108. [2953-count-complete-substrings]

  109. [2958-length-of-longest-subarray-with-at-most-k-frequency]

  110. [2962-count-subarrays-where-max-element-appears-at-least-k-times]

  111. [2968-apply-operations-to-maximize-frequency-score]

  112. [2981-find-longest-special-substring-that-occurs-thrice-i]

  113. [2982-find-longest-special-substring-that-occurs-thrice-ii]

  114. [3013-divide-an-array-into-subarrays-with-minimum-cost-ii]

  115. [3023-find-pattern-in-infinite-stream-i]

  116. [3037-find-pattern-in-infinite-stream-ii]

  117. [3086-minimum-moves-to-pick-k-ones]

  118. [3090-maximum-length-substring-with-two-occurrences]

  119. [3095-shortest-subarray-with-or-at-least-k-i]

  120. [3097-shortest-subarray-with-or-at-least-k-ii]

  121. [3134-find-the-median-of-the-uniqueness-array]

  122. [3135-equalize-strings-by-adding-or-removing-characters-at-ends]

  123. [3191-minimum-operations-to-make-binary-array-elements-equal-to-one-i]

  124. [3206-alternating-groups-i]

  125. [3208-alternating-groups-ii]

  126. [3234-count-the-number-of-substrings-with-dominant-ones]

  127. [3254-find-the-power-of-k-size-subarrays-i]

  128. [3255-find-the-power-of-k-size-subarrays-ii]

  129. [3258-count-substrings-that-satisfy-k-constraint-i]

  130. [3261-count-substrings-that-satisfy-k-constraint-ii]

  131. [3297-count-substrings-that-can-be-rearranged-to-contain-a-string-i]

  132. [3298-count-substrings-that-can-be-rearranged-to-contain-a-string-ii]

  133. [3305-count-of-substrings-containing-every-vowel-and-k-consonants-i]

  134. [3306-count-of-substrings-containing-every-vowel-and-k-consonants-ii]

  135. [3318-find-x-sum-of-all-k-long-subarrays-i]

  136. [3321-find-x-sum-of-all-k-long-subarrays-ii]

  137. [3323-minimize-connected-groups-by-inserting-interval]

  138. [3325-count-substrings-with-k-frequency-characters-i]

  139. [3329-count-substrings-with-k-frequency-characters-ii]

  140. [3346-maximum-frequency-of-an-element-after-performing-operations-i]

  141. [3347-maximum-frequency-of-an-element-after-performing-operations-ii]

  142. [3364-minimum-positive-sum-subarray]

  143. [3411-maximum-subarray-with-equal-products]

  144. [3413-maximum-coins-from-k-consecutive-bags]

  145. [3420-count-non-decreasing-subarrays-after-k-operations]

  146. [3422-minimum-operations-to-make-subarray-elements-equal]

  147. [3439-reschedule-meetings-for-maximum-free-time-i]

  148. [3445-maximum-difference-between-even-and-odd-frequency-ii]

  149. [3505-minimum-operations-to-make-elements-within-k-subarrays-equal]

整体思路

滑动窗口算法的抽象思想：

// @author D瓜哥 · https://www.diguage.com
int left = 0, right = 0;

while (right < s.size()) {
    window.add(s[right]);
    right++;

    while (valid) {
        window.remove(s[left]);
        left++;
    }
}

其中 window 的数据类型可以视具体情况而定，比如上述题目都使用哈希表充当计数器，当然你也可以用一个数组实现同样效果，因为我们只处理英文字母。

稍微麻烦的地方就是这个 valid 条件，为了实现这个条件的实时更新，我们可能会写很多代码。比如前两道题，看起来解法篇幅那么长，实际上思想还是很简单，只是大多数代码都在处理这个问题而已。

常见题目

  1. Subarray Sum Equals K - LeetCode

参考资料

  1. 滑动窗口通用思想解决子串问题 - 找到字符串中所有字母异位词

  2. Java优化labuladong大佬滑动窗口通用方法 - 找到字符串中所有字母异位词

  3. 面试官，你再问我滑动窗口问题试试？我有解题模板，不怕！

  4. 滑动窗口【基础算法精讲 03】

  5. 713. 乘积小于 K 的子数组 - 官方思路秒懂○注释详细○双指针滑窗 【附通用滑窗模板】

  6. 904. 水果成篮 - 【深度解析】这道题和76. 最小覆盖子串的区别 — 这个题解比较了“最大滑动窗口”和“最小滑动窗口”的区别。可以研究一下。

← Previous: QuickSelect 快速选择 | ↑ Up: LeetCode 解题笔记 | Next: Monotonic Stack 单调栈 →