信息
- ID
- 76
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者
暴力枚举,复杂度 O(n3)。即枚举以 i 开头,以 j 结尾的区间,并 O(n) 求和
预处理出前缀和数组 sum[i],同样还是枚举区间,求和的复杂度降到了 O(1),总的复杂度为 O(n2)
考虑每一个数会被多少个区间包括。
例如:3 个数 [1,2,3]。包括 1 的区间有 [1,1],[1,2],[1,3],包括 2 的区间有 [1,2],[1,3],[2,2],[2,3] 共四个。
对于每个位置 i,包含 A[i] 的区间共有 i∗(n−i+1) 个,所以 A[i] 被统计了 i∗(n−i+1) 次。
用这个方法计算,时间复杂度为 O(n)。