题意分析

题目要求我们找到一个由连续元素组成的子序列，使得该子序列的和大于或等于给定的整数S，并且这个子序列的长度尽可能短。如果有多个满足条件的子序列，我们需要返回其中长度最小的那个；如果没有满足条件的子序列，则返回0。

解题思路

1. 前缀和数组：首先，我们计算前缀和数组sum，其中sum[i]表示从第一个元素到第i个元素的和。这样，任意子序列的和可以通过sum[r] - sum[l-1]快速计算出来。
2. 二分查找：为了找到最小的长度，我们可以使用二分查找的方法。我们设定一个可能的长度范围（1到n），然后检查是否存在一个长度为mid的子序列满足和大于等于S。如果存在，则尝试更小的长度；否则，尝试更大的长度。
3. 滑动窗口优化：实际上，这个问题还可以用滑动窗口（双指针）的方法在O(n)的时间内解决，比二分查找的O(n log n)更高效。滑动窗口通过动态调整窗口的左右边界来寻找满足条件的最短子序列。

标程

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

int solve() {
    int n, S;
    cin >> n >> S;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    
    int min_len = INT_MAX;
    int left = 0;
    int current_sum = 0;
    
    for (int right = 0; right < n; ++right) {
        current_sum += nums[right];
        while (current_sum >= S) {
            min_len = min(min_len, right - left + 1);
            current_sum -= nums[left];
            left++;
        }
    }
    
    return min_len == INT_MAX ? 0 : min_len;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        cout << solve() << '\n';
    }
    
    return 0;
}

代码解释

1. 输入处理：使用cin读取输入的测试用例数量T，然后对于每个测试用例，读取序列的长度n和目标值S，以及序列本身。
2. 滑动窗口：
   • left指针表示窗口的左边界，right指针表示窗口的右边界。
   • current_sum维护当前窗口内元素的和。
   • 遍历数组时，right指针向右移动，扩展窗口，增加current_sum。
   • 当current_sum大于等于S时，尝试缩小窗口（移动left指针）以找到更小的满足条件的窗口长度。
3. 结果输出：如果找到满足条件的窗口，输出最小长度；否则输出0。

这种方法确保了在最坏情况下时间复杂度为O(n)，适用于较大的输入规模。