查看“滑动窗口方法”的源代码

滑动窗口方法（Sliding Window Technique）是指在数据结构（通常是数组或字符串）中移动固定或可变大小的窗口，以基于连续元素子集有效地解决问题的技术。

===Abstract===
#使用兩個指針（left, right）表示一個窗口，left 指針表示窗口的起始位置，right 指針表示窗口的結束位置。
#隨著右指針逐步移動，擴大窗口，當遇到重複字符時，按顺序縮小窗口，直到窗口内不再有重复字符。

===说明===
#目前窗口中含有字符 X。当 right 移动遇到下一个字符 X 时，left 滑动到第一个 X 的下一个位置，使当前窗口中不再有重复字符；
#left 滑动前窗口中的字符串与已经保存的最长子串对比/替换；
{| class="wikitable"
|+#1
!left
!
!
!
!
!right
!
!
|-
|O
|O
|X
|O
|O
|O
|X
|O
|}
Max=OOXOOO, window=OOXOOO, MaxLength=6
{| class="wikitable"
|+#2
!
!
!
!left
!
!
!right
!
|-
|O
|O
|X
|O
|O
|O
|X
|O
|}
Max=OOXOOO, window=OOOX, MaxLength=6

以上图例中，O 代表任何字符，在上文中，显然除了最后一个 O，其他所有的 O 都不重复。

===Time Complexity===
一般来说这些问题可以使用嵌套循环在 O(N<sup>2</sup>) 时间复杂度中解决，使用滑动窗口可以在 O(N) 时间复杂度中解决这些问题。 

===应用===
*最长无重复子串
*最小覆盖子串（所有给定字符都至少出现一次）
*子串和问题

===Leetcode - 003===
 <3. Longest Substring Without Repeating Characters
 Medium
 
 Given a string s, find the length of the longest substring without repeating characters.
 
 Example 1:
 Input: s = "abcabcbb"
 Output: 3
 Explanation: The answer is "abc", with the length of 3.
 
 Example 2:
 Input: s = "bbbbb"
 Output: 1
 Explanation: The answer is "b", with the length of 1.
 
 Example 3:
 Input: s = "pwwkew"
 Output: 3<
 Explanation: The answer is "wke", with the length of 3.
 Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
 
 Constraints:
     0 <= s.length <= 5 * 10^4
     s consists of English letters, digits, symbols and spaces.
 
 Accepted 6.6M, Submissions 18.5M, Acceptance Rate 35.8%</small>

 <small><nowiki>public static int lengthOfLongestSubstring(String s) {
    int[] charIndex = new int[128];
    for (int i = 0; i < 128; i++) {
        charIndex[i] = -1;
    }

    int maxLength = 0;
    int left = 0;
    for (int right = 0; right < s.length(); right++) {
        char currentChar = s.charAt(right);
        if (charIndex[currentChar] >= left) {
            left = charIndex[currentChar] + 1;
        }

        charIndex[currentChar] = right;
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}</nowiki></small>

== See Also ==

# [https://www.geeksforgeeks.org/window-sliding-technique/ Sliding Window Technique]

[[分类:Develop]]
[[分类:Algorithm]]