Sliding Window Algorithm in C++

The sliding window algorithm is a common technique used for solving problems that involve finding a substring, subarray, or subsequence that satisfies certain conditions. It involves maintaining a “window” of elements within a larger sequence and adjusting the window’s boundaries based on the problem’s constraints. This technique can be used to optimize various algorithms, such as those dealing with strings, arrays, or sequences.

Here’s a general outline of how the sliding window algorithm works:

1. Initialization: Initialize two pointers (usually called left and right) that define the current window’s boundaries. Set them to the start of the sequence.
2. Expand the Window: Move the right pointer to expand the window to the right while satisfying a specific condition. This can mean adding elements to the window.
3. Shrink the Window: While the condition is no longer satisfied, move the left pointer to shrink the window from the left. This can mean removing elements from the window.
4. Update Solution: As the window moves and changes, track or update the solution based on the content of the current window.
5. Repeat: Continue steps 2 to 4 until the right pointer reaches the end of the sequence.

Here’s a simple example of using the sliding window algorithm to find the maximum sum of a subarray of fixed size k within an array:

#include <iostream>
#include <vector>

int maxSubarraySum(const std::vector<int>& nums, int k) {
    int maxSum = 0;
    int currentSum = 0;

    // Calculate the initial sum of the first k elements
    for (int i = 0; i < k; ++i) {
        currentSum += nums[i];
    }
    maxSum = currentSum;

    // Slide the window
    for (int i = k; i < nums.size(); ++i) {
        currentSum = currentSum - nums[i - k] + nums[i];
        maxSum = std::max(maxSum, currentSum);
    }

    return maxSum;
}

int main() {
    std::vector<int> nums = {2, 1, 5, 1, 3, 2};
    int k = 3;

    int result = maxSubarraySum(nums, k);
    std::cout << "Maximum sum of a subarray of size " << k << ": " << result << std::endl;

    return 0;
}

In this example, the sliding window algorithm maintains a window of size k that slides through the array. It calculates the initial sum of the first k elements and then updates the sum by subtracting the leftmost element and adding the rightmost element for each step. The maximum sum encountered during the sliding process is the desired result.

The sliding window algorithm can be adapted and extended to solve various other problems involving substrings, subarrays, or subsequences that satisfy certain conditions.