题意
给定 nnn 个数字的数组,找到长度恰好为 kkk 的连续子段,使其区间总和最小。若存在多个和相同的最小区间,输出起始下标最小的那个(下标从 111 开始)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
思路
1.1.1. 构建前缀和数组sss,s[i]s[i]s[i] 表示前 iii 个元素总和,区间 [l,r][l,r][l,r] 和为 s[r]−s[l−1]s[r]-s[l-1]s[r]−s[l−1]。
2.2.2. 遍历所有合法起点 iii(满足 i+k−1≤ni+k-1 ≤ ni+k−1≤n ),计算每个长度为 kkk 的区间和;
3.3.3. 记录当前最小和 minnminnminn 以及对应起始下标 idxidxidx:
\quad ∘\circ∘ 若当前区间和 <<< 最小和:更新最小和,更新下标;
\quad ∘\circ∘ 若当前区间和 === 最小和:无需操作(因为遍历顺序从左到右,先出现的下标更小,保留原有 idxidxidx 即可);
4.4.4. 遍历结束输出记录的起始下标。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
完整代码