牛客 NC221681 dd 爱框框：滑动窗口实战解析

题目描述

给定一个整数数组和一个目标值 x，需要找到一个最短的连续子数组，使得该子数组的元素之和大于等于 x。如果存在多个满足条件的子数组，输出起始和结束位置（从 1 开始计数）。

解题思路

这道题如果用双重循环暴力枚举，时间复杂度会达到 O(n²)，在数据量大时容易超时。核心优化点在于利用滑动窗口（双指针）技术，将复杂度降为 O(n)。

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

1. 扩展窗口：初始时 cur 从左向右移动，每移动一步就将 arr[cur] 加入 sum。
2. 收缩窗口：一旦 sum >= x，说明当前窗口满足条件。此时我们需要尝试缩小窗口以寻找更短的长度。具体做法是不断移除 arr[prev] 并移动 prev 指针，直到 sum < x 为止。在这个过程中，每次满足条件时都更新最优解的位置。
3. 重复直至结束：当 cur 遍历完整个数组后，算法结束。

关键点在于，当 sum >= x 时，不仅要记录当前的长度，还要尝试通过移动左指针来进一步缩短区间，因为可能存在更优解。

代码实现

下面是完整的 C++ 实现，注意处理索引偏移和边界情况。

#include <iostream>

  std;

{
    
     n, x;
    cin >> n >> x;
    
    ;
     ( i = ; i < n; i++) {
        cin >> arr[i];
    }

    
     index[] = {};
    
    
     cur = ;      
     prev = ;     
     sum = ;      

     (cur < n) {
        sum += arr[cur];
        
        
         (sum >= x) {
            
             (index[] ==  && index[] == ) {
                index[] = prev;
                index[] = cur;
                sum -= arr[prev++];
                ;
            }
            
            
             length = index[] - index[];
             camplen = cur - prev;
            
            
             (length == camplen || length > camplen) {
                 (prev < index[] || length > camplen) {
                    index[] = prev;
                    index[] = cur;
                }
            }
            
            
            sum -= arr[prev++];
        }
        
        
        cur++;
    }

    
    cout << index[] +  <<  << index[] +  << endl;
     ;
}