我知道一个 O(n2) 的解决方案，它可以用更好的方式完成吗，因为数组中元素的数量限制是 <=100,000
最佳答案
是的，如果所有元素都是非负的，则有一个 O(n lgn) 算法。
- 定义
p[i]是p[0..i]的总和(我们称之为前缀和) - 对于每个
i: 二进制搜索最大值j这样p[j] - p[i-1] <= k, 添加j-i+1到柜台
总复杂度为 O(n) + O(n lgn) = O(n lgn)
之所以有效，是因为对于每个 i ，我们试图找到从 i 开始的最大范围这样这个范围的总和是 <= k。
让这个范围是[i..j] ，因为所有元素都是非负的，所以 [i..i], [i..i+1], [i..i+2] ... [i..j]都是和<= k的子数组，总共有j-i+1他们中的。
我们为每个 i 找到了这样的范围, 从i开始不断增加子数组的个数哪个总和 <= k
关于algorithm - 总和小于或等于给定 'k' 的子数组数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35781390/