滑動窗口演算法在演算法面試題中的應用

試想有這樣一道題， 怎麼解決?

題目描述：

給定兩個字元串s和t， 找到s中包含所有t中字母的最短字元串組合。

舉例：

輸入: S = 「ADOBECODEBANC」, T = ABC

輸出: 「BANC」

這個時候就要用到滑動窗口演算法，滑動窗口演算法廣泛應用於網路協議等，其實滑動窗口演算法是一種思路，可以解決很多問題。

下面詳細講解下這個演算法的步驟：

設定兩個指針，left和right，表示一個滑動的窗口之最左端和最右端。

初始，這兩個指針指向S的第一個字元

left不動，right來向右移動，直到找到一個字元串能匹配T串，便是當前能match的字元串。

這個時候，我們一個一個的右移動left，同時每右移動一次left，我們再通過右移動right來找match的字元串，如果能找到，且比當前串短，update。如果找不到，繼續右移動left。

下面舉例說明一下：

left=0， right=0;ADOBECODEBANC

移動right, 找到第一個match的字元串:

右移動left一步，一直移動right，找到match字元串，但是更長，不更新，

繼續右移動left一位，

最後找到了最短字元串BANC

同樣的思路可以解決如下問題：

A. 給定一個字元串s和一個非空字元串p，在s中找到p字謎的所有開始索引。

s: 「cbaebabacd」 p: 「abc」 輸出[0,6]

B. 給定一個字元串，查找不重複字元的最長子字元串的長度。

left=0,right=0;

歡迎留言交流!

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！