2360. 滑动窗口
1000ms
256MB
简单
前缀和与差分
题目描述
给定一个含有 $n$ 个整数的数组和一个正整数 $K$。请计算并输出所有长度为 $K$ 的连续子区间的元素总和。
输入格式
- 第一行包含两个正整数 $n$ 和 $K$ ($1 \le K \le n \le 500000$)，分别表示数组长度和连续子区间的长度。
- 第二行包含 $n$ 个非负整数 $a_i$ ($0 \le a_i \le 100$)，表示数组中的元素，数与数之间用空格隔开。
输出格式
- 输出一行，包含 $n - K + 1$ 个整数，分别表示每个长度为 $K$ 的连续子区间之和，数字之间用空格隔开。
样例 1
输入 (Input)
10 3 2 1 3 6 4 5 8 7 0 9
输出 (Output)
6 10 13 15 17 20 15 16
样例说明
- **样例说明**：
在含有 10 个数字的数组中，长度为 3 的连续子区间和依次为：
- $2 + 1 + 3 = 6$
- $1 + 3 + 6 = 10$
- $3 + 6 + 4 = 13$
- $6 + 4 + 5 = 15$
- $4 + 5 + 8 = 17$
- $5 + 8 + 7 = 20$
- $8 + 7 + 0 = 15$
- $7 + 0 + 9 = 16$
- 对于 $100\%$ 的数据：$1 \le K \le n \le 500000$，且 $0 \le a_i \le 100$。
- **算法提示**：
若使用暴力法，重复计算重叠部分的和会导致超时（TLE）。
建议使用**滑动窗口**算法：
1. 先求出前 $K$ 个元素（区间 $[0, K-1]$）的和 $S_0$ 并输出。
2. 随后窗口向右滑动。对于下一个区间，其和可通过递推公式得到：$S_{i} = S_{i-1} - a_{i-1} + a_{i+K-1}$（即减去移出窗口的左侧元素，加上新进入窗口的右侧元素）。
3. 通过这一递推关系，每次滑动只需进行一次减法和一次加法操作，复杂度降为 $O(N)$。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功