[已解决]尺取法-最短子串和

player-none

题目描述
给定一个由n个整数组成的数字串num，并给出一个值S，现请你求出num中元素和大于等于S的最短子串的长度并输出，若没有则输出0。
输入描述
3行，第1行包含1个数字n,代表数字的个数n。
第2行包含n个数字,代表数字串中的每一个数字。
第3行包含1个数字S,代表需要比较的值S
输出描述
1行，包含num中元素和大于等于S的最短子串的长度。
样例1
输入
10
1 2 4 6 3 4 1 2 3 5
9
输出
2
提示
5<=n<=100000,1<=S<=9999998，数字大小不超过100。

我的代码

1. #include <iostream>
   
2. using namespace std;
   
3. int a[100005];
   
4. int main()
   
5. {
   
6.     int n,s;
   
7.     cin>>n;
   
8.     for(int i=0;i<n;++i)
   
9.         cin>>a[i];
   
10.     cin>>s;
    
11.     int minl=n,flag=0;
    
12.     for(int l=0;l<n;++l){
    
13.         for(int r=l;r<l+minl;++r){
    
14.             int sum=0;
    
15.             for(int i=l;i<=r;++i){
    
16.                 sum+=a[i];
    
17.             }
    
18.             if(sum>=s) {
    
19.                 minl=min(minl,r-l+1);
    
20.                 flag=1;
    
21.             }
    
22.         }
    
23.     }
    
24.     if(!flag){
    
25.         minl=0;
    
26.     }
    
27.     cout<<minl;
    
28.         return 0;
    
29. }

复制代码

超时问题，如何简化

最佳答案

月排行榜 / 总排行榜

FishC

2025-5-23 22:09:40

解答

这道题可以用滑动窗口（尺取法）高效解决。核心思路是维护一个窗口，通过调整左右边界寻找满足条件的最短子串。

算法步骤：

• 初始化左指针 left=0 和当前和 sum=0，最小长度设为 n+1
• 遍历数组，右指针 right 逐步扩展窗口，将元素加入 sum
• 当 sum >= S 时，尝试缩小左边界，记录最小窗口长度
• 最终若找到合法窗口，输出最小长度；否则输出 0
  

1. 
   
2. #include <iostream>
   
3. #include <vector>
   
4. using namespace std;
   
5. 
   
6. int main() {
   
7.     int n;
   
8.     cin >> n;
   
9.     vector<int> nums(n);
   
10.     for (int i = 0; i < n; ++i) cin >> nums[i];
    
11.     int S;
    
12.     cin >> S;
    
13.    
    
14.     int left = 0, sum = 0, min_len = n + 1;
    
15.     for (int right = 0; right < n; ++right) {
    
16.         sum += nums[right];
    
17.         while (sum >= S) {
    
18.             min_len = min(min_len, right - left + 1);
    
19.             sum -= nums[left++];
    
20.         }
    
21.     }
    
22.     cout << (min_len <= n ? min_len : 0) << endl;
    
23.     return 0;
    
24. }
    

复制代码

关键点解释：
1. 滑动窗口通过动态调整左右边界，确保时间复杂度为 O(n)
2. 当窗口和满足条件时，持续缩小左边界以寻找更优解
3. 初始将最小长度设为 n+1 便于后续判断是否存在合法解

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

player-none

@FishC

player-none

FishC 发表于 2025-5-23 22:10
（当用户具体提问时，我会根据问题类型采用以下格式结构作答）

示例问答演示：

不是 你 prompt 随便骗的吗