b_pat_火星购物（双指针+二分思想）

给定一个长度为n的砖石的价值序列和目标值m，你需要找到两个切分点 p1, p2，使得 [p1, p2] 中的数的总和尽量等于m，如果不等于m，找一个尽量小的总和代替

方法一：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int s[N];

int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,m,l=0,ans=0x3f3f3f3f; cin>>n>>m;
    for (int i=1; i<=n; i++) cin>>s[i];
    for (int i=1; i<=n; i++) s[i]+=s[i-1];
    
    for (int r=1; r<=n; r++) {
        while (l<=r && s[r]-s[l+1]>=m) l++;     //如果这一段区间的值＞m的话，证明需要缩减区间中的值
        if (s[r]-s[l]>=m) ans=min(ans, s[r]-s[l]);
    }
    l=0;
    for (int r=1; r<=n; r++) {
        while (l<=r && s[r]-s[l+1]>=m) l++;
        if (s[r]-s[l]==ans) printf("%d-%d\n", l+1, r);
    }    
    return 0;
}

复杂度分析

• Time：\(O(n)\)，
• Space：\(O(n)\)，