How the Sliding Window Technique Is Applied Across LeetCode Problems

The sliding window technique uses two pointers to maintain a dynamic subarray or substring, expanding the right boundary until a condition is violated, then contracting the left boundary to restore validity, achieving O(n) time complexity.

The LeetCodeAnimation repository by MisterBooo demonstrates this pattern through detailed algorithmic explanations and visual animations. By examining the source files and embedded code snippets, developers can see how a single template adapts to variable-size subarrays, fixed-size windows, and monotonic deque optimizations.

What Is the Sliding Window Technique?

A sliding window maintains a dynamic interval [left … right] (or [l … r]) over the input data.

• Expansion: Move the right boundary forward until a constraint is violated.
• Contraction: Move the left boundary forward to restore the constraint.
• Recording: Capture the optimal answer (longest, shortest, or valid window) during traversal.

Because each element enters and exits the window exactly once, the time complexity is O(n) and auxiliary space is typically O(1) (or O(k) when a hash set or deque is required).

Sliding Window Applications in the Repository

The repository implements the sliding window technique across multiple problem categories, each demonstrating a specific variation of the pattern.

Variable-Size Windows: Longest Substring Without Repeating Characters (Problem 3)

In notes/LeetCode第3号问题：无重复字符的最长子串.md, the algorithm tracks the longest substring with all unique characters.

The window expands by moving right forward while checking a frequency array. When a duplicate appears, left slides past the previous occurrence of the duplicate character.

// Excerpt from the repository implementation
if (r + 1 < s.size() && freq[s[r+1]] == 0) {
    r++;
    freq[s[r]]++;
} else {
    freq[s[l]]--;
    l++;
}
res = Math.max(res, r - l + 1);

Minimum Size Subarray Sum (Problem 209)

The file notes/LeetCode第209号问题：长度最小的子数组.md uses the sliding window to find the smallest contiguous subarray with a sum greater than or equal to s.

The right pointer expands until the sum meets the target, then the left pointer contracts to minimize the window size while maintaining the sum condition.

if (r + 1 < nums.length && sum < s) {
    r++;
    sum += nums[r];
} else {
    sum -= nums[l];
    l++;
}
if (sum >= s) result = Math.min(result, r - l + 1);

The repository includes animation files like 0ga4f.gif to visualize this expansion and contraction process.

Fixed-Size Windows: Contains Duplicate II (Problem 219)

In notes/LeetCode第219号问题：存在重复元素II.md, the window size is constrained to k. The algorithm checks if any value appears at least twice within an index distance of k.

A hash set maintains the current window contents. As the window slides one step forward, the outgoing element is removed from the set and the incoming element is checked for existence.

while (right + 1 < nums.length) {
    right++;
    if (!set.add(nums[right])) return true;
    if (right - left + 1 > k) set.remove(nums[left++]);
}
return false;

Sliding Window Maximum with Deque (Problem 239)

The file notes/LeetCode第239号问题：滑动窗口最大值.md demonstrates the monotonic deque optimization for fixed-size windows.

A double-ended queue stores indices in decreasing order of their corresponding values. The front of the deque always holds the maximum of the current window. As the window slides, indices outside the window are popped from the front, and new elements are added from the back after removing smaller elements.

while (!deque.isEmpty() && nums[deque.getLast()] < nums[i]) 
    deque.removeLast();
deque.addLast(i);
if (deque.getFirst() == i - k) 
    deque.removeFirst();
if (i >= k - 1) 
    res[i - k + 1] = nums[deque.getFirst()];

The repository provides animations such as 8ggd3.gif to illustrate how the deque evolves as the window moves across the array.

Generic Sliding Window Template

Based on the implementations in notes/LeetCode第3号问题：无重复字符的最长子串.md and notes/LeetCode第209号问题：长度最小的子数组.md, the following Java skeleton captures the common pattern:

int left = 0, right = -1;          // Current window: nums[left … right]
while (left < nums.length) {       // Left bound stays inside array
    // 1️⃣ Expand: move right while condition is not yet satisfied
    if (right + 1 < nums.length && !conditionSatisfied()) {
        right++;
        // update data structures (sum, hash map, deque, …) with nums[right]
    } else {
        // 2️⃣ Shrink: condition satisfied or right at end → move left
        // update data structures by removing nums[left]
        left++;
    }
    // 3️⃣ (Optional) Record answer based on current window
    // answer = …;
}

This template adapts to variable-size problems by adjusting the termination condition, or to fixed-size problems by maintaining a window of exactly k elements.

Summary

• The sliding window technique reduces time complexity from O(n²) to O(n) by ensuring each element enters and exits the window exactly once.
• The LeetCodeAnimation repository demonstrates this pattern across variable-size substrings (Problem 3), minimum-length subarrays (Problem 209), fixed-size duplicate detection (Problem 219), and monotonic deque optimizations (Problem 239).
• Each implementation follows a consistent template using left and right pointers, with specific data structures (hash sets, deques, frequency arrays) chosen based on the constraint requirements.
• Visual animations embedded in the markdown files (e.g., 0ga4f.gif, 8ggd3.gif) illustrate the window movement and pointer adjustments, reinforcing the algorithmic logic.

Frequently Asked Questions

What is the time complexity of the sliding window technique?

The sliding window technique achieves O(n) time complexity because each element in the input array or string is visited at most twice—once when the right pointer expands the window and once when the left pointer contracts it. This linear performance is explicitly documented in the repository’s solution files, such as notes/LeetCode第209号问题：长度最小的子数组.md, which states "时间复杂度: O(n)".

When should I use a deque versus a hash set in sliding window problems?

Use a hash set when you need to track the existence of elements within the current window to detect duplicates, as seen in notes/LeetCode第219号问题：存在重复元素II.md for Problem 219. Use a monotonic deque when you need to query the maximum or minimum value of the current window in O(1) time, as demonstrated in notes/LeetCode第239号问题：滑动窗口最大值.md for Problem 239, where the deque stores indices in decreasing order of their values.

How does the sliding window differ from the two-pointer technique?

While both techniques use two indices, the sliding window specifically maintains a contiguous subarray or substring defined by a left and right boundary that moves monotonically forward through the input. The two-pointer technique often refers to pointers starting at opposite ends moving toward each other (e.g., binary search or finding a pair sum in a sorted array), or non-contiguous intervals. The repository’s implementations in files like notes/LeetCode第3号问题：无重复字符的最长子串.md explicitly treat the left and right pointers as a dynamic window over a contiguous string segment.

Can the sliding window technique handle negative numbers?

The standard sliding window technique described in the repository assumes monotonicity or specific constraints that allow the left pointer to move forward without reconsidering previous elements. When negative numbers are present, the sum of a subarray is no longer monotonic with respect to the right pointer, meaning shrinking the window from the left might actually increase the sum. Therefore, the simple sliding window template from notes/LeetCode第209号问题：长度最小的子数组.md (which assumes positive integers) would fail. Problems with negative numbers typically require prefix sums or other techniques rather than the classic sliding window approach.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}