如何用前缀和与双指针技巧解决PAT甲级1044购物在火星问题？

本文共计500个文字，预计阅读时间需要2分钟。

题目：求和问题输入：输入一个正整数N（N=1e5）和一个正整数M（M=1e8），然后输入N个正整数（每个数不超过1e3）。输出：按照升序输出所有连续整数段[i-j]，其中i~j的和等于M或是最小的等于M的大整数段。

代码：pythondef find_segments(N, M, numbers): # 初始化最小长度为无穷大 min_length=float('inf') # 初始化最小长度对应的起始位置 start_index=0

# 遍历所有可能的起始位置 for i in range(N): # 初始化当前段的和 current_sum=0 # 遍历当前段的所有可能结束位置 for j in range(i, N): # 累加当前段的和 current_sum +=numbers[j] # 如果当前段的和等于M，更新最小长度和起始位置 if current_sum==M: if j - i + 1 M: break

# 输出结果 for i in range(start_index, start_index + min_length): print(i, end=' ') print()

输入N=int(input())M=int(input())numbers=list(map(int, input().split()))

调用函数find_segments(N, M, numbers)

题意：

输入一个正整数N和M（N<=1e5,M<=1e8），接下来输入N个正整数（<=1e3），按照升序输出"i-j"，i~j的和等于M或者是最小的大于M的数段。

代码：

#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
int a[100007];
int sum[100007];
vector<pair<int,int> >ans;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i){
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
int l=0,t=0,mn=1e9;
for(int i=0;i<=n;++i){
t-=a[i];
while(t<m&&l<=n)
t+=a[l++];
if(t>=m&&t<mn){
mn=t;
ans.clear();
ans.push_back({i+1,l-1});
}
else if(t==mn)
ans.push_back({i+1,l-1});
}
cout<<ans[0].first<<"-"<<ans[0].second;
for(int i=1;i<ans.size();++i)
cout<<"\n"<<ans[i].first<<"-"<<ans[i].second;
return 0;
}