<aside> 📌 Key Points:

• Key question to answer for Sliding Window problem ⇒ Is this best I can do?
• Sliding Window Key Definitions：
  • effective window range: [slow, fast)
  • Linear Traversal using Two Pointers (fast/slow)
    • slow pointer is to ensure window meets its requirement. (i.e. window size = k, at most 2 repeating char …)
    • fast pointer is to traverse entire array/string to ensure all possibile solutions are considered.
• Fixed Size Sliding Window vs. Non-Fixed Size Sliding Window
  • Fixed Size: move slow to ensure window meets the window size requirement: fast - slow == k
  • Non-Fixed Size: move slow to ensure sliding window meets the window criteria (minimum/maximum, longest, shortest, distinct, repeating…)
• Sliding Window Keywords:
  • find min/max/longest/shortest/repeating/distinct values in subarray/substring
  • contain k-length/k-typed/k-repeating/k-distinct elements
  • find longest subarray sums equals to k (prefixSum), longest subarray sum greater than or equals to k (sliding window)
  • find frequency of each character in subarray greater than or equals to k
  • String permutation: target string exists in source string </aside>

<aside> 🎯 Sliding Window 题型 & 模版：

Overall，
// step1: 需要什么data structure?
	repeating => HashMap<Character, count>   //frequency map
	distinct => matched && HashMap<Character, count> 
	subarray sum => curSum || HashMap<prefixSum, index>

// step 2: 两个指针同向而行，search all possibile solutions
slow = 0
for (fast = 0; fast < n; fast++) {
	// step 3: 先加fast去考虑这个新的值怎么去影响当前的sliding window
	add fast
	
	// step 4: 查看当前值满足sliding window条件？需要移动slow去收缩window space？
	while (meeting sliding window condition) {
		// step 5: update res when window meets its criteria
		update res
		remove slow
		slow++
	}
}
return res if found

• Longest/Shortest题
• Minimum/Maximum Average/Sum/Product/Count 题
• Find Repeated/Distinct Values题
• Sliding Window 延伸版 </aside>

<aside> ✍️ 易错点：

• longest/shortest题更新globalValue的时候， 最后一定要先update longest/shortest 再fast++(longest = Math.max(longest, fast - slow + 1);，再 fast++;
  • ⇒ better to use for loop for fast traversal instead of while loop to in case i forget to move fast++
• Sliding Window + HashMap Combination题：
  • remove slow过程中，如果遇到一个<key, value>, value changes from 1 to 0 -> remove pair from map to decrease map’s size
  • 每次动fast 或者 slow，别忘了update 指针对应的其他变量，i.e map, matched.. etc
  • string题的题目里讲到肯定有26个字母only的话，可以用array来取代hashmap
• 移动指针 ⇒ 过一个完整的例子去清楚的理解什么时候动指针，该怎么动之后再写代码。
• 变量scope ⇒ 想好global scope还是在loop里的local scope。 i.e. Longest Subarray with Equal Number of 1s and 0s 和 Longest String with At Least K Repeating Char都要在loop里面initialize变量。
• 逻辑要捋清 ⇒ nested if or nested while？最好不好nested 结构 i.e. Minimum Window Substring
• Subarray题，问自己，里面有duplicate会不会影响结果？i.e. Count Number of Nice Subarrays
• 不熟悉的API
  • substring(beginIndex, endIndex) ⇒ “abcde”.substring(1, 3); //”bc”, 包括beginIndex不包括endIndex
  • map.remove(keyName) </aside>

<aside> 🌵 Table of Contents

</aside>

Maximum/Minimum Average/Sum/Product/Count

Date: July 7, 2023

Problem: Maximum Average Subarray I (Fixed Size Sliding Window)

Date: July 7, 2023

Problem: Maximum Average Subarray II （巧妙 - Binary Search w/o Sort）

Date: July 7, 2023

Problem: Maximum Size Subarray Sum Equals to K (PrefixSum + HashMap)

Date: July 7, 2023

Problem: Minimum Size Subarray Sum (Greater than or Equal to K) Non-fixed Size Sliding Window