Sliding Window
Sliding Window Overview
Related Questions
- Minimum Size Subarray Sum
- 本题成立的条件是所有的数都是positive
- Longest Substring Without Repeating Characters
- Minimum Window Substring
- Find All Anagrams in a String
- Substring with Concatenation of All Words
- Longest Substring with At Most Two Distinct Characters
- Subarrays with K Different Integers
- Longest Substring with At Most K Distinct Characters
- Sliding Window Maximum
- Longest Repeating Character Replacement
- Permutation in String
- Count Unique Characters of All Substrings of a Given String
- Fruit Into Baskets
- Minimum Number of K Consecutive Bit Flips
- Longest Repeating Character Replacement
Longest Substring with At Most K Distinct Characters 这个问题有一个简便的思路是，用一个(key, rightPosition)的HashMap来替代（key, frequency）的HashMap.
Subarrays with K Different Integers 方便求at most K different integer, 所以我们可以采用prefix sum的思路来处理。注意 right - left = 当前最多依然使用的是prefix sum
Code
1 int count = map.size(); //record element
2 int left = 0, right = 0;
3 List<Integer> res = new ArrayList<>();
4 while (right < s.length()){
5 char ch = s.charAt(right);
6 if (map.containsKey(ch)){
7 map.put(ch, map.get(ch) - 1);
8 if (map.get(ch) == 0) count--;
9 }
10 right++;
11 while (count == 0){
12 //condition to record results
13 if (right - left == p.length()){
14 res.add(left);
15 }
16 ch = s.charAt(left);
17 if (map.containsKey(ch)){
18 map.put(ch, map.get(ch) + 1);
19 if (map.get(ch) == 1) count++;
20 }
21 left++;
22 }
23 }