use*_*412 0 algorithm time-complexity data-structures
我知道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