Sliding Window

發表於 | 分類於 ，

two pointer 雙指針 O(N)

題目

  • 3 Longest Substring Without Repeating Characters (Medium)
  • 76 Minimum Window Substring (Hard)
  • 438 Find All Anagrams in a String (Medium)
  • 567 Permutation in String (Medium)
  • 239 Sliding Window Maximum (Hard)
  • 424 Longest Repeating Character Replacement (Medium)

補充

    1. Maximum Average Subarray I (Easy)
    1. Maximum Number of Vowels in a Substring of Given Length (Medium)
  • 187 Repeated DNA Sequences
  • 209 Minimum Size Subarray Sum
  • *713 Subarray Product Less Than K
  • 632 Smallest Range Covering Elements from K Lists (Hard)
  • 1004 Max Consecutive Ones III (Medium)
  • *30 Substring with Concatenation of All Words (Hard)
  • 209 Minimum Size Subarray Sum
  • *632. Smallest Range Covering Elements from K Lists
  • 395 Longest Substring with At Least K Repeating Characters
  • 1695 Maximum Erasure Value (Medium)

移動窗口框架

1
2
3
4
5
6
7
8
9
10
11
12
13
int left = 0, right = 0;

while (right < s.size()) {`
    // 增大窗口
    window.add(s[right]);
    right++;

    while (window needs shrink) {
        // 縮小窗口
        window.remove(s[left]);
        left++;
    }
}