滑动窗口方法

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

Abstract

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

说明

1. 目前窗口中含有字符 X。当 right 移动遇到下一个字符 X 时，left 滑动到第一个 X 的下一个位置，使当前窗口中不再有重复字符；
2. left 滑动前窗口中的字符串与已经保存的最长子串对比/替换；

#1

left					right
O	O	X	O	O	O	X	O

Max=OOXOOO, window=OOXOOO, MaxLength=5

#2

			left			right
O	O	X	O	O	O	X	O

Max=OOXOOO, window=OOOX, MaxLength=5

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

Time Complexity

一般来说这些问题可以使用嵌套循环在 O(N²) 时间复杂度中解决，使用滑动窗口可以在 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%

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;
}

See Also

1. Sliding Window Technique