寻找区间和

尺取法产生变化的滑动窗口， 同向扫描。

给一个长度为 $n$ 的数组 $a$ 和一个数 $s$， 找一个长度最小的连续的区间， 使其区间和等于 $s$。

思路

若枚举所有长度的区间， 是 $O(N^2)$ 复杂度。

可以用尺取法：

假设所有数都是正整数， 对于区间 $[i,j]$ ， 设其区间和为 $sum$, 当 $sum\ge s$ 时， 令 $i++$， 同时 $sum-=a_i$ 。 若 $sum<s$ 时， 令 $j++$, 同时 $sum+=a_j$ 。如果 $i>j$ ， 则 $j++$, 且置 $sum=a_i$。

因为找的区间时连续的， 因此如果 当前的 $[i,j]$ 区间和 $sum\ge s$ ， 那么后续的 $j+1,j+2,\dots ,j+k$ 都会 $sum\ge s$ 。因此， 若想找的是 $sum=s$ 的区间， 必须抛弃掉 $a_i$。

那么假如有负数呢？很好办， 定义 $X=min负数$ 为序列中最小的负数， 然后对所有数 $a_i+=|X|$， 即做一个偏移， 让所有数都为整数， 因此可以证明包含负数情况跟正整数情况相同。

是 $>=s$ 的最小区间

题目：https://vjudge.csgrandeur.cn/problem/POJ-3061#author=rainty7

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
 
typedef long long LL;
 
const int N = 2e5 + 10;
LL a[N];
LL q[N], f[N];
 
void solve() {
    LL n,m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
 
    LL sum = a[1], res = 0x3f3f3f3f;
    LL i = 1, j = 1;
    while(j <= n)
    {   
        //cout << i << " " << j << " " << sum <<  endl;
        if(sum >= m)
        {
            
            res = min(j - i + 1, res);
            sum -= a[i];
            i++;
            if(i > j) {sum = a[i], j++;}
        }
        if(sum < m) {j++;sum += a[j];}
        
    }
    if(res >= 0x3f3f3f3f / 2) cout << 0 << endl;
    else 
    cout << res << endl;
 
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--)
    solve();
    return 0;
}

区间和绝对值与t之差最小

https://vjudge.csgrandeur.cn/problem/POJ-2566#author=CCUT_1816

 
 
```asd