算法题解：牛客 NC221681 dd 爱框框

问题描述

给定一个包含 n 个整数的数组和一个目标值 x，需要找到一个连续子数组，使其元素之和大于等于 x。如果有多个满足条件的子数组，通常希望找到长度最短的一个。

解题思路

这道题如果采用暴力枚举所有子数组的方法，时间复杂度会达到 O(n^2)，在数据量较大时容易超时。我们可以利用滑动窗口（双指针）的策略将效率优化到 O(n)。

具体做法是维护两个指针 prev 和 cur，分别代表窗口的左边界和右边界。同时用一个变量 sum 来记录当前窗口内元素的总和。

当 sum 小于 x 时，说明当前窗口还不够大，无法覆盖目标值，此时需要扩大窗口，让 cur 向右移动并累加新加入的元素。

一旦 sum 达到或超过 x，我们就找到了一个满足条件的窗口。为了寻找更短的窗口，我们需要尝试收缩左边界，即让 prev 向右移动，并从 sum 中减去移出的元素。在这个过程中，如果发现了比之前记录的更短的有效窗口，就更新最佳位置。

重复上述过程直到 cur 遍历完整个数组。

代码实现

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 读取输入规模 n 和目标值 x
    int n, x;
    cin >> n >> x;

    vector<int> arr(n);
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 用于存储最终结果的起始和结束索引
    // 初始化为 0，表示尚未找到有效区间
    int index[2] = {0};
    
    // 滑动窗口初始化
    int cur = 0;      // 右指针
    int prev = 0;     // 左指针
    int sum = 0;      // 当前窗口和

    while(cur < n) {
        sum += arr[cur]; // 扩展右边界
        
        // 当窗口和满足条件时，尝试收缩左边界以寻找更优解
        while(sum >= x) {
            // 如果是第一次找到有效窗口，直接记录
            if(index[0] == 0 && index[1] == 0) {
                index[0] = prev;
                index[1] = cur;
                sum -= arr[prev++];
                continue;
            }

            // 比较当前窗口长度与已记录的最短长度
            // 注意：index 存储的是下标，长度计算需考虑偏移
            int currentLen = cur - prev + 1;
            int bestLen = index[1] - index[0] + 1;

            // 如果当前更短，则更新最佳记录
            if(currentLen < bestLen) {
                index[0] = prev;
                index[1] = cur;
            }
            
            // 收缩左边界
            sum -= arr[prev++];
        }
        cur++; // 继续扩展右边界
    }

    // 输出结果（转换为 1-based 索引）
    cout << index[0] + 1 << " " << index[1] + 1 << endl;
    return 0;
}

关键点说明

1. 双指针协作：cur 负责探索新的可能性，prev 负责在满足条件后尝试优化结果。两者都只向右移动，保证了线性时间复杂度。
2. 状态重置：sum 随着窗口的伸缩动态变化，不需要重新计算区间和，这是滑动窗口高效的关键。
3. 边界处理：注意数组下标从 0 开始，但题目通常要求输出 1-based 的索引，记得在最后输出时加 1。