算法思路
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⁵ 的要求