An Introduction to Sliding Window Algorithms

March 11, 2022 · 1 min · Gray King

tags: Sliding Window
source: Moore, Jordan. “An Introduction to Sliding Window Algorithms.” Medium, July 26, 2020. https://levelup.gitconnected.com/an-introduction-to-sliding-window-algorithms-5533c4fe1cc7.

Efficientive algorithm:

Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away. – Antoine de Saint-Exupéry

The following return values can use a sliding window:

Minimum value
Maximum value
Longest value
Shortest value
K-sized value

And contiguous is one of the biggest clues.

Common data structures are strings, arrays and even linked lists.

Framework:

Slide right window to move forward
Slide left window to meet the requirements.
Compare to result.

Links to this note

LeetCode101: 3. Longest Substring Without Repeating Characters

tags: Sliding Window,LeetCode101,Hash Table Use HashMap to store counts of letters Two points we should be noticed: The length of substring should be (right - left) + 1, as one side must be counted. We must decrese the number in the counts first, and then slide the left window, or we must decrese the wrong one, please compare between Wrong and Correct. Wrong left++; counts[s[left]]--; Correct counts[s[left]]--; left++; The full code see:...