定长区间总和
2026-01-16 10:49:52
发布于:浙江
19阅读
0回复
0点赞
算法思路
- 问题理解
题目要求:计算所有长度为 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
- 前缀和技术
前缀和数组 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]
- 代码流程
读取输入: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;
}
全部评论 2
good
21小时前 来自 江苏
0d
1周前 来自 浙江
0













有帮助,赞一个