問(wèn)題
已知一個(gè)長(zhǎng)度為n的數(shù)組（允許負(fù)數(shù)）, 和一個(gè)整數(shù)k, 求：和小于k的最長(zhǎng)連續(xù)子串拾碌？
例如:
k=184, A=[431, -15, 639, 342, -14, 565, -924, 635, 167, -70],
和小于184的最長(zhǎng)子串為A[3..6]
寫(xiě)個(gè)簡(jiǎn)單測(cè)試先
require_relative '../longest_subarray_with_sum_less_than_k'
describe LongestSub do
let(:array) {[431, -15, 639, 342, -14, 565, -924, 635, 167, -70]}
let(:bound) {184}
let(:result) {subject.longest(array,bound)}
let(:ans) {array[3..6]}
it "should compute the longest subarray whose sum <= bound" do
expect(result).to eq ans
end
end
分析
如果暴力枚舉起點(diǎn)和終點(diǎn)，復(fù)雜度為O(n^2)橄镜。能不能找到一些規(guī)律優(yōu)化呢臭埋？
Make hands dirty
單純考慮原數(shù)組好像找不到規(guī)律蛇捌。
考慮前綴和毕贼，此時(shí)問(wèn)題轉(zhuǎn)換為已知pre數(shù)組，求pre[j]-pre[i]<=k的距離最大(i,j)對(duì).
由于有負(fù)數(shù)拄衰，pre數(shù)組沒(méi)有遞增規(guī)律它褪。
第一個(gè)元素的右端點(diǎn)，就已經(jīng)難以確定了翘悉，必須從右到左掃描茫打，直到差值<=k，有可能一個(gè)都不成功；而且老赤，算好i后轮洋，算i＋1時(shí)好像還是要掃描所有之后的右端點(diǎn)。
于是考慮對(duì)pre排序, 然后可以用“雙指針”抬旺，不斷移動(dòng)右指針直到>k弊予，并一直保存當(dāng)前最右下標(biāo)。這樣需要復(fù)雜度O(nlogn)排序＋O(n) == O(nlogn)
Make it better
還有更好的方法嗎开财？有沒(méi)有什么規(guī)律汉柒，來(lái)排除一些值呢？
可以發(fā)現(xiàn)右端點(diǎn)中责鳍，如果j1<j2而且pre[j1]>=pre[j2]碾褂，那肯定不會(huì)選j1, 因?yàn)閖2既比j1遠(yuǎn)，求和時(shí)結(jié)果又比j1小薇搁。所以斋扰，可以從右到左掃描一遍渡八，過(guò)濾掉不可能的右端點(diǎn)啃洋。
而且發(fā)現(xiàn)，這樣過(guò)濾后的右端點(diǎn)在pre上是遞增的屎鳍，就可以用“雙指針”求了宏娄。
復(fù)雜度 = O(n)過(guò)濾 + O(n)掃描 ＝ O(n)
代碼：
class LongestSub
def longest(arr,bound)
reset(arr,bound)
l,r = [(0...size),poss_r].map(&:to_enum)
loop { update(l,r) }
arr[@longest_range]
end
def update(l, r)
i,j = [l,r].map(&:peek)
if i<=j && presum(j,i)<=bound
@longest_range = [@longest_range, (i..j)].max_by(&:size)
r.next
else
l.next
end
end
private
attr_reader :arr, :bound
def reset(arr,bound)
@arr,@bound=[arr,bound]
@poss_r = @pre = nil
@longest_range = (0...0)
end
def size; arr.size end
def pre
@pre ||= arr.reduce([0]){|res,v| res << res.last+v}
end
def presum(j,i=0)
pre[j+1] - pre[i]
end
def poss_r
@poss_r ||= (0...size).reverse_each.reduce([]) do |res,i|
res.unshift(i) unless res.first && presum(i) >= presum(res.first)
res
end
end
end
