如何在線性時間內爲給定k找到包含所有元素1至k的最小子陣列

Question

假設數組爲{2 4 2 1 5 3 5 3}且k = 3。 subarray {2 1 5 3}包含1 2 3.

我想知道是否有線性時間算法來解決這個問題。

Answer 1

是的，有：

begin = -1 
end = -1 
best = 0 
new = 1 
finalbegin = -1 
finalend = -1 
for i = 1 to n 
    if (new and input[i] >= 1 and input <= k) 
     begin = i 
     new = 0 
    end if 
    if (new and (input[i] <= 1 or input[i] >= k) or (i = n)) 
     if (input[i] <= 1 or input[i] >= k) 
      end = i - 1 
     else 
      end = i 
     end if 
     new = 1 
     if (end - begin >= best) 
      finalbegin = begin 
      finalend = end 
      best = end - begin + 1 
     end if 
    end if 
end for 

無論何時你發現一個新的區間，你檢查它是否比已經找到了最好，只有更好。如果是這樣，你把它當作新的最好的。如果開始和結束是否定的，那麼空集是解決方案。否則最好找到解決辦法