如何实现环形滑动窗口？求环形数组滑动窗口最小和

要覆盖包含数组末尾与开头元素的环形滑动窗口，我们可以通过两种高效方式修改原有代码，以下是具体实现思路和代码：

方法一：取模模拟环形数组（滑动窗口优化版） #

通过取模运算模拟数组的环形结构，无需额外创建扩展数组，保持O(n)的时间复杂度：

#include <iostream>
#include <algorithm>
#include <climits>

int minsum(int arr[], int n, int k)
{
    if (n < k)
        return -1;
    // 当窗口大小等于数组长度时，直接返回数组总和
    if (k == n) {
        int total = 0;
        for (int i = 0; i < n; ++i)
            total += arr[i];
        return total;
    }

    // 计算第一个窗口（起始位置0）的和
    int current_sum = 0;
    for (int i = 0; i < k; ++i) {
        current_sum += arr[i];
    }
    int min_sum = current_sum;

    // 滑动遍历所有可能的窗口起始位置（1到n-1）
    for (int start = 1; start < n; ++start) {
        // 移除窗口左侧的元素
        current_sum -= arr[start - 1];
        // 添加环形结构下窗口右侧的新元素（通过取模实现首尾衔接）
        current_sum += arr[(start + k - 1) % n];
        min_sum = std::min(min_sum, current_sum);
    }

    return min_sum;
}

int main()
{
    int arr[] = {1, 2, 5, 4, 3};
    int k = 3;
    int n = sizeof(arr) / sizeof(arr[0]);
    std::cout << minsum(arr, n, k) << std::endl; // 输出6，对应窗口{3,1,2}的和
    return 0;
}

思路说明 #

• 利用(start + k - 1) % n计算环形结构下窗口右侧的元素索引，实现数组首尾的无缝衔接；
• 滑动窗口时，仅需移除窗口左侧的旧元素、添加右侧的新元素，避免重复计算窗口内所有元素，保证效率。

方法二：总和转换法（数学优化版） #

环形窗口的和可以通过数组总和减去长度为n-k的线性窗口的最大和得到，因此求最小环形窗口和等价于求总和减去最大的n-k长度线性窗口和：

#include <iostream>
#include <algorithm>

int minsum(int arr[], int n, int k)
{
    if (n < k)
        return -1;
    if (k == n) {
        int total = 0;
        for (int i = 0; i < n; ++i)
            total += arr[i];
        return total;
    }

    // 计算数组总和
    int total_sum = 0;
    for (int i = 0; i < n; ++i)
        total_sum += arr[i];

    // 求长度为m = n - k的线性窗口的最大和
    int m = n - k;
    int current_max_sum = 0;
    for (int i = 0; i < m; ++i)
        current_max_sum += arr[i];
    int max_sum = current_max_sum;

    for (int i = m; i < n; ++i) {
        current_max_sum += arr[i] - arr[i - m];
        max_sum = std::max(max_sum, current_max_sum);
    }

    // 最小环形窗口和 = 数组总和 - 最大的m长度窗口和
    return total_sum - max_sum;
}

int main()
{
    int arr[] = {1, 2, 5, 4, 3};
    int k = 3;
    int n = sizeof(arr) / sizeof(arr[0]);
    std::cout << minsum(arr, n, k) << std::endl; // 输出6
    return 0;
}

思路说明 #

• 对于环形窗口（包含首尾元素），其对应的补集是一个长度为n-k的线性窗口；
• 最小的环形窗口和 = 数组总和 - 最大的补集窗口和，利用这个数学关系将问题转化为已解决的线性窗口最大和问题。

内容的提问来源于stack exchange，提问作者dfgl