arrays - 線形時間で指定された k に対して少なくとも 1 回は 1 から k までのすべての要素を含む最小のサブ配列を見つける方法

Question

配列が {2 4 2 1 5 3 5 3} で、k=3 であるとします。サブ配列 {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

新しい間隔を見つけるたびに、それが既に見つかった最良のものよりも優れているかどうかを確認します。もしそうなら、あなたはそれを新しい最高のものとして扱います。begin と end が負の場合、空のセットが解になります。それ以外の場合は、最善の解決策が見つかります