文章
20
粉丝
147
获赞
13
访问
51.7k
这个题数据量比较大,是1e5,
题目要求找有多少个全为1长度至少为M的子串,
其实本质就是找连续1的数量,
假设M是3
如果找到一段连续1的长度小于3,那么答案就是0
如果找到一段连续1的长度是3,那么答案就是1
如果找到一段连续1的长度是4,那么答案就是2+1=3
如果找到一段连续1的长度是5,那么答案就是3+2+1=6
...
推导出
如果找到一段连续1的长度是k,那么答案就是1+2+3+....+(n-3+1)
这是一个累加和公式,ans = (n-3+1) * (n-3+1 + 1) / 2
换成M就是ans = (n-M+1) * (n-M+2) / 2
最终把所有的ans全部加起来,也就是所有的不同长度的连续1的结果和。
时间复杂度是线性的,也就是O(1e5)
登录后发布评论
暂无评论,来抢沙发