尺取法-最短子串和
题目描述给定一个由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。
我的代码
#include <iostream>
using namespace std;
int a;
int main()
{
int n,s;
cin>>n;
for(int i=0;i<n;++i)
cin>>a;
cin>>s;
int minl=n,flag=0;
for(int l=0;l<n;++l){
for(int r=l;r<l+minl;++r){
int sum=0;
for(int i=l;i<=r;++i){
sum+=a;
}
if(sum>=s) {
minl=min(minl,r-l+1);
flag=1;
}
}
}
if(!flag){
minl=0;
}
cout<<minl;
return 0;
}
超时问题，如何简化 @FishC 解答
这道题可以用滑动窗口（尺取法）高效解决。核心思路是维护一个窗口，通过调整左右边界寻找满足条件的最短子串。
算法步骤：
[*]初始化左指针 left=0 和当前和 sum=0，最小长度设为 n+1
[*]遍历数组，右指针 right 逐步扩展窗口，将元素加入 sum
[*]当 sum >= S 时，尝试缩小左边界，记录最小窗口长度
[*]最终若找到合法窗口，输出最小长度；否则输出 0
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; ++i) cin >> nums;
int S;
cin >> S;
int left = 0, sum = 0, min_len = n + 1;
for (int right = 0; right < n; ++right) {
sum += nums;
while (sum >= S) {
min_len = min(min_len, right - left + 1);
sum -= nums;
}
}
cout << (min_len <= n ? min_len : 0) << endl;
return 0;
}
关键点解释：
1. 滑动窗口通过动态调整左右边界，确保时间复杂度为 O(n)
2. 当窗口和满足条件时，持续缩小左边界以寻找更优解
3. 初始将最小长度设为 n+1 便于后续判断是否存在合法解
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 player-none 发表于 2025-05-23 22:09
@FishC
好的，我明白了！我会严格按照Discuz!的BBCode格式规范来回答问题。遇到代码示例时会用标签包裹，行内代码用底色高亮，重点内容用加粗/斜体，保持段落间距确保易读性。遇到复杂问题会分步骤用列表呈现。请鱼油们随时提问吧~
（当用户具体提问时，我会根据问题类型采用以下格式结构作答）
示例问答演示：
Python如何读取文件内容？
可以按照以下步骤操作：
[*]使用 open() 函数打开文件
[*]选择读取模式（如 'r' 表示读取）
[*]调用 read() 方法获取内容
[*]最后关闭文件
示例代码：
with open('data.txt', 'r') as f:
content = f.read()
print(content)
注意：使用 with 语句可以自动处理文件关闭，更安全推荐
遇到问题欢迎继续提问！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 FishC 发表于 2025-5-23 22:10
（当用户具体提问时，我会根据问题类型采用以下格式结构作答）
示例问答演示：
不是 你 prompt 随便骗的吗 解答
这道题可以使用尺取法（双指针法）高效解决。核心思路是通过维护左右指针动态调整窗口大小，找到满足条件的最短子串。
n = int(input())
num = list(map(int, input().split()))
S = int(input())
min_len = n + 1# 初始化为不可能的最大值+1
current_sum = 0
left = 0
for right in range(n):
current_sum += num
# 当满足条件时，尝试缩小区间
while current_sum >= S:
min_len = min(min_len, right - left + 1)
current_sum -= num
left += 1
print(min_len if min_len <= n else 0)
关键步骤解析：
[*]初始化左指针 left=0 和当前和 current_sum=0
[*]右指针 right 从左到右遍历数组，累加元素值
[*]当和 ≥S 时，不断右移左指针缩小区间，同时更新最小长度
[*]最终检查是否存在有效解，若存在返回最小长度，否则返回0
时间复杂度为 O(n)，空间复杂度为 O(1)。此解法适用于元素均为正数的场景，能高效处理大规模数据。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 大佬厉害，算法
页:
[1]