尺取法-最短子串和

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. }

复制代码

超时问题，如何简化

player-none

@FishC

FishC

解答

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

算法步骤：

• 初始化左指针 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 小助理，如未能正确解答您的问题，请继续追问。

FishC

player-none 发表于 2025-05-23 22:09
@FishC

[quote]
好的，我明白了！我会严格按照Discuz!的BBCode格式规范来回答问题。遇到代码示例时会用

1. 标签包裹，行内代码用底色高亮，重点内容用加粗/斜体，保持段落间距确保易读性。遇到复杂问题会分步骤用列表呈现。请鱼油们随时提问吧~
   
2. [/quote]
   
3. 
   
4. （当用户具体提问时，我会根据问题类型采用以下格式结构作答）
   
5. 
   
6. 示例问答演示：
   
7. 
   
8. [size=3][b]Python如何读取文件内容？[/b][/size]
   
9. 
   
10. 可以按照以下步骤操作：
    
11. 
    
12. [list]
    
13. [*]使用 [backcolor=#eee]open()[/backcolor] 函数打开文件
    
14. [*]选择读取模式（如 [backcolor=#eee]'r'[/backcolor] 表示读取）
    
15. [*]调用 [backcolor=#eee]read()[/backcolor] 方法获取内容
    
16. [*]最后关闭文件
    
17. [/list]
    
18. 
    
19. 示例代码：
    
20. [code]
    
21. with open('data.txt', 'r') as f:
    
22.     content = f.read()
    
23.     print(content)
    

复制代码

注意：使用 with 语句可以自动处理文件关闭，更安全推荐

遇到问题欢迎继续提问！

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

player-none

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

示例问答演示：

不是 你 prompt 随便骗的吗

FishC

解答

这道题可以使用尺取法（双指针法）高效解决。核心思路是通过维护左右指针动态调整窗口大小，找到满足条件的最短子串。

1. 
   
2. n = int(input())
   
3. num = list(map(int, input().split()))
   
4. S = int(input())
   
5. min_len = n + 1  # 初始化为不可能的最大值+1
   
6. current_sum = 0
   
7. left = 0
   
8. 
   
9. for right in range(n):
   
10.     current_sum += num[right]
    
11.     # 当满足条件时，尝试缩小区间
    
12.     while current_sum >= S:
    
13.         min_len = min(min_len, right - left + 1)
    
14.         current_sum -= num[left]
    
15.         left += 1
    
16. 
    
17. print(min_len if min_len <= n else 0)
    

复制代码

关键步骤解析：

• 初始化左指针 left=0 和当前和 current_sum=0
• 右指针 right 从左到右遍历数组，累加元素值
• 当和 ≥S 时，不断右移左指针缩小区间，同时更新最小长度
• 最终检查是否存在有效解，若存在返回最小长度，否则返回0
  

时间复杂度为 O(n)，空间复杂度为 O(1)。此解法适用于元素均为正数的场景，能高效处理大规模数据。

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

爬虫121

大佬厉害，算法