acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 竞赛
  • 讨论
  • 团队
  • 商城
登录
注册
题目详情提交记录(0)
  • 定长区间总和

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

    userId_undefined
    yeye
    10月全勤卷王11月全勤卷王12月全勤卷王1月全勤卷王时空双修者
    19阅读
    2回复
    3点赞
  • 第一条题解!!!!!

    题很简单啊,只需要会前缀和就好了,不过记得是i到i+k还要-1的啊qwp

    userId_undefined
    枫岚
    秩序白银出道萌新快乐小狗时空双修者GESP4级
    25阅读
    1回复
    2点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页