數比之和小於或等於給定的數k

Question

我知道一個O（N 2）SOLN，可以將它以更好的方式來完成，如無元件的極限子陣列的在陣列是巨大的是< = 100,000

Answer 1

是的，如果所有元素都是非負的，則存在O（n lgn）算法。

1. 定義p[i]是p[0..i]總和（我們稱之爲前綴和）
2. 對於每個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