定长区间总和

算法思路

1. 问题理解

题目要求：计算所有长度为 k 的连续子数组的和，然后将这些和相加。

例如：n=5, k=3, 数组 [1,2,3,4,5]

子数组1: [1,2,3] 和=6

子数组2: [2,3,4] 和=9

子数组3: [3,4,5] 和=12

总和 = 6+9+12 = 27

2. 前缀和技术

前缀和数组 a：

a[0] = 0

a[i] = 数组前 i 个元素的和

例如：a[3] = a[0]+a[1]+a[2]+a[3] = 0+1+2+3 = 6

如何计算区间和：

区间 [i, j] 的和 = a[j] - a[i-1]

长度为 k 的区间 [i, i+k-1] 的和 = a[i+k-1] - a[i-1]

3. 代码流程

读取输入：n, k 和数组元素

构建前缀和数组：

边读入边计算前缀和

a[i] 存储前 i 个元素的和

计算总和：

遍历所有可能的起始位置 i

区间 [i, i+k-1] 对应前缀和索引 [i, i+k-1]

但代码中循环变量是区间的结束位置

实际上，循环从 i=k 到 n，计算区间 [i-k+1, i] 的和

区间和 = a[i] - a[i-k]

累加所有区间和
4. 时间复杂度

构建前缀和：O(n)

计算区间和总和：O(n-k+1) ≈ O(n)

总时间复杂度：O(n)，满足 n≤2×10⁵ 的要求

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,k;
    cin>>n>>k;
    long long int a[n+1];
    a[0]=0;  // 前缀和数组初始化为0
    for(long long int i=1;i<=n;i++)
    {
        long long int aa;
        cin>>aa;
        a[i]=a[i-1]+aa;  // 计算前缀和
    }
    long long int c=0;
    for(long long int i=k;i<=n;i++)
        c+=(a[i]-a[i-k]);  // 计算每个长度为k的区间和并累加
    cout<<c;
    return 0;
}