Sliding Window Technique

Sliding window technique is useful for solving problems in array or string, especially it is considered as a technique that could reduce the time complexity from O(n²) to O(n).

There are two types of sliding window:

1. Fixed window length k: the length of the window is fixed and it asks you to find something in the window such as the maximum sum of all windows, the maximum or median number of each window. Usually we need kind of variables to maintain the state of the window, some are as simple as a integer or it could be as complicated as some advanced data structure such as list, queue or deque.
2. Two pointers + criteria: the window size is not fixed, usually it asks you to find the subarray that meets the criteria, for example, given an array of integers, find the number of subarrays whose sum is equal to a target value.

Some problems

1. Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Solution: the problem falls into the first type of sliding window problems, since the length of the window is fixed. We find the first window with size k and maintain a variable curSum which equals the sum of all the elements within the current window and a global maxSum which is the maximum sum among all the windows we have examined. As we moving the window one step at a time from left to right, we subtract the leftmost element in the…