3.2 雙指針

第2章用兩個指針來定位一個子數(shù)組，其中一個指針指向數(shù)組的第1個數(shù)字，另一個指針指向數(shù)組的最后一個數(shù)字，那么兩個指針之間所包含的就是一個子數(shù)組。

如果將字符串看成一個由字符組成的數(shù)組，那么也可以用兩個指針來定位一個子字符串，其中一個指針指向字符串的第1個字符，另一個指針指向字符串的最后一個字符，兩個指針之間所包含的就是一個子字符串。

可以在移動這兩個指針的同時，統(tǒng)計兩個指針之間的字符串中字符出現(xiàn)的次數(shù)，這樣可以解決很多常見的面試題，如在一個字符串中定位另一個字符串的變位詞等。

由于這種類型的面試題都與統(tǒng)計字母出現(xiàn)的次數(shù)有關(guān)，我們經(jīng)常使用哈希表來存儲每個元素出現(xiàn)的次數(shù)，因此解決這種類型的面試題通常需要同時使用雙指針和哈希表。

面試題14：字符串中的變位詞

分析：變位詞是與字符串相關(guān)的面試題中經(jīng)常出現(xiàn)的一個概念。所謂的變位詞是指組成各個單詞的字母及每個字母出現(xiàn)的次數(shù)完全相同，只是字母排列的順序不同。例如，"pots"、"stop"和"tops"就是一組變位詞。

由變位詞的定義可知，變位詞具有以下幾個特點。首先，一組變位詞的長度一定相同；其次，組成變位詞的字母集合一定相同，并且每個字母出現(xiàn)的次數(shù)也相同。

這個題目如果不考慮時間復雜度，用暴力法就可以解決。實際上，一個字符串的變位詞是字符串的排列。可以先求出字符串s1的所有排列，然后判斷每個排列是不是字符串s2的子字符串。如果一個字符串有n個字符，那么它一共有n！（n的階乘）個排列，因此這種解法的時間復雜度不會低于O（n！）。

下面嘗試尋找更高效的算法。既然題目是關(guān)于變位詞的，而變位詞與字母及字母出現(xiàn)的次數(shù)有關(guān)，那么就應該統(tǒng)計字符串中包含的字母及每個字母出現(xiàn)的次數(shù)。如果一個哈希表的鍵是字母，而哈希表中的值是對應字母出現(xiàn)的次數(shù)，那么這樣一個哈希表很適合用來統(tǒng)計字符串中每個字母出現(xiàn)的次數(shù)。

由于這個題目強調(diào)字符串中只包含英文小寫字母，而英文小寫字母的個數(shù)是確定的，一共26個，因此可以用數(shù)組模擬一個簡單的哈希表。數(shù)組的下標0對應字母'a'，它的值對應字母'a'出現(xiàn)的次數(shù)。數(shù)組的下標1對應字母'b'，它的值對應字母'b'出現(xiàn)的次數(shù)。以此類推，數(shù)組的下標25對應字母'z'，它的值對應字母'z'出現(xiàn)的次數(shù)。

首先掃描字符串s1。每掃描到一個字符，就找到它在哈希表中的位置，并把它對應的值加1。如果字符串s1為"ac"，那么掃描該字符串并統(tǒng)計每個字母出現(xiàn)的次數(shù)之后的哈希表如圖3.1（a）所示。在該哈希表中，只有字母'a'和字母'c'對應的值是1，其他值都是0，這是因為只有這兩個字母在字符串中各出現(xiàn)了1次。

然后考慮如何判斷字符串s2中是否包含字符串s1的變位詞。假設字符串s2中有一個子字符串是字符串s1的變位詞，逐個掃描這個變位詞中的字母，并把字母在哈希表中對應的值減1。由于字符串s1的變位詞和字符串s1包含相同的字母，并且每個字母出現(xiàn)的次數(shù)也相同，因此掃描完字符串s1的變位詞之后，哈希表中所有的值都是0。

字符串s1的變位詞和字符串s1的長度一樣。假設字符串s1的長度是n，下面逐一判斷字符串s2中長度為n的子字符串是不是字符串s1的變位詞。判斷的辦法就是掃描子字符串中的每個字母，把該字母在哈希表中對應的值減1。如果哈希表中的所有值是0，那么該子字符串就是字符串s1的一個變位詞。

下面以字符串"dgcaf"為s2作為例子來逐步分析這個過程。可以用雙指針來定位一個子字符串，其中一個指針指向子字符串的第1個字符，另一個指針指向子字符串的最后一個字符。首先，雙指針定位的子字符串為"dg"。如果掃描該子字符串中的兩個字母'd'和'g'，那么在哈希表中把它們對應的值減1。此時哈希表的狀態(tài)如圖3.1（b）所示。

接下來把這兩個指針都向右移動1位，讓它們定位子字符串"gc"。每次移動這兩個指針時都相當于在原來的子字符串的最右邊添加一個新的字符，并且從原來子字符串中刪除最左邊的字符。每當在子字符串中添加一個字符時，就把哈希表中對應位置的值減1。同樣，每當在子字符串中刪除一個字符時，就把哈希表中對應位置的值加1。在把字母'c'的值減1、字母'd'的值加1之后，哈希表的狀態(tài)如圖3.1（c）所示。

再把兩個指針都向右移動1位，讓它們定位子字符串"ca"。這相當于在原來子字符串"gc"的最右邊添加字母'a'，同時刪除最左邊的字母'g'。在把字母'a'的值減1、字母'g'的值加1之后，哈希表的狀態(tài)如圖3.1（d）所示。此時哈希表中所有的值都是0，因此這兩個指針指向的子字符串就是字符串s1的一個變位詞。

可以基于雙指針和哈希表的思路編寫如下所示的代碼：

在上述函數(shù)checkInclusion中，第2個for循環(huán)中的下標i相當于第2個指針，指向子字符串的最后一個字符。第1個指針指向下標為i-s1.length()的位置。兩個指針之間的子字符串的長度一直是字符串s1的長度。

上述基于雙指針和哈希表的算法需要掃描字符串s1和s2各一次。如果它們的長度分別是m和n，那么該算法的時間復雜度是O（m+n）。這種解法用到了一個數(shù)組。數(shù)組的長度是英文小寫字母的個數(shù)（即26），是一個常數(shù)，也就是說，數(shù)組的大小不會隨著輸入字符串長度的變化而變化，因此空間復雜度是O（1）。

面試題15：字符串中的所有變位詞

分析：這個題目是面試題14的變種，所以也可以用一個哈希表來統(tǒng)計字符串s2中字母出現(xiàn)的次數(shù)。由于字母的總數(shù)是已知的，一共有26個英文小寫字母，因此可以用一個長度為26的數(shù)組模擬一個哈希表。

如果字符串s2的長度為n，則逐個統(tǒng)計字符串s1中所有長度為n的子字符串中字母出現(xiàn)的次數(shù)。可以用兩個指針來定位字符串s1的子字符串，第1個指針指向字符串的第1個字符，第2個指針指向字符串的最后一個字符。每次統(tǒng)計完子字符串中字符出現(xiàn)的次數(shù)之后，兩個指針同時向右移動一位。兩個指針每向右移動一位，相當于在上一次的子字符串的最右邊加上一個字母，并刪除原來子字符串最左邊的字母。

每當在子字符串中添加一個字母，則把哈希表中該字母對應的值減1；每當從子字符串中刪除一個字母，則把哈希表中該字母對應的值加1。如果哈希表中所有的值都是0，那么由兩個指針定位的子字符串是字符串s2的一個變位詞。按照題目要求，把第1個指針對應的下標添加到結(jié)果鏈表中。

由于這種思路和面試題14的思路基本一致，因此不再一步步分析。這種思路的參考代碼如下所示：

輔助函數(shù)areAllZero和面試題14的代碼中的一樣，所以此處不再重復介紹。

同樣，這種解法的時間復雜度也是O（n），空間復雜度是O（1）。

面試題16：不含重復字符的最長子字符串

分析：和前面的題目一樣，此處還是用一個哈希表統(tǒng)計子字符串中字符出現(xiàn)的次數(shù)。如果一個子字符串中不含重復的字符，那么每個字符都只出現(xiàn)一次，它們在哈希表中對應的值為1。沒有在子字符串中出現(xiàn)的其他字符對應的值都是0。也就是說，如果子字符串中不含重復字符，那么它對應的哈希表中沒有比1大的值。

下面仍然用兩個指針來定位一個子字符串，其中第1個指針指向子字符串的第1個字符，第2個指針指向子字符串的最后一個字符。接下來分析如何移動這兩個指針。

如果兩個指針之間的子字符串不包含重復的字符，由于目標是找出最長的子字符串，因此可以向右移動第2個指針，在子字符串的最右邊增加新的字符，然后判斷新的字符在子字符串中有沒有重復出現(xiàn)。如果還是沒有重復的字符，則繼續(xù)向右移動第2個指針，在子字符串中添加新的字符。

例如，在字符串"babcca"中找最長的不含重復字符的子字符串時，兩個指針都初始化指向第1個字符'b'，此時子字符串為"b"，不含重復字符（表3.2中的第1步）。于是向右移動第2個指針使其指向字符'a'，此時子字符串為"ba"，仍然不含重復字符（表3.2中的第2步）。于是再次向右移動第2個指針使其指向字符'b'。

如果兩個指針之間的子字符串中包含重復的字符，則可以向右移動第1個指針，刪除子字符串中最左邊的字符。如果刪除最左邊的字符之后仍然包含重復的字符，則繼續(xù)向右移動第1個指針刪除最左邊的字符。例如，表3.2中的第3步，兩個指針之間的字符串是"bab"，有重復出現(xiàn)的字符，于是向右移動第1個指針使其指向字符'a'。

如果刪除最左邊的字符之后不再包含重復的字符，就可以向右移動第2個指針，在子字符串的右邊添加新的字符。例如，表3.2中的第4步，此時兩個指針之間的字符串是"ab"，沒有重復出現(xiàn)的字符，于是向右移動第2個指針使其指向字符'c'，得到最長的不含重復字符的子字符串。

之后的步驟如表3.2所示，請讀者自行一步步分析。

? 需要多次遍歷整個哈希表的解法

在厘清上述思路之后，編寫代碼就會比較容易。參考代碼如下所示：

由于這個題目沒有說明字符串中只包含英文字母，那么就有可能包含數(shù)字或其他字符，因此字符就可能不止26個。假設字符串中只包含ASCII碼的字符。由于ASCII碼總共有256個字符，因此用來模擬哈希表的數(shù)組的長度就是256。

需要注意的是，每次調(diào)用函數(shù)hasGreaterThan1都可能需要掃描一次數(shù)組counts。雖然數(shù)組counts的長度是常數(shù)256，但掃描一次的時間是O（1），因此這個常數(shù)還是有點大。下面介紹避免多次遍歷整個哈希表的解法。

? 避免多次遍歷整個哈希表的解法

我們真正關(guān)心的是哈希表中有沒有比1大的數(shù)字，因為如果有大于1的數(shù)字就說明子數(shù)組中包含重復的數(shù)字。可以定義一個變量countDup來存儲哈希表中大于1的數(shù)字的個數(shù)，即子字符串中重復字符的個數(shù)。每次向右移動第2個指針使子字符串包含更多字符時都會把哈希表中對應的數(shù)字加1。當一個字符對應的數(shù)字從1變成2時，表示該字符重復出現(xiàn)了，因此變量countDup加1。

當向右移動第1個指針刪除子字符串中最左邊的字符時，都會把哈希表中對應的數(shù)字減1。當一個字符對應的數(shù)字由2變成1時，該字符不再重復出現(xiàn)，因此變量countDup減1。

根據(jù)這個優(yōu)化思路編寫的代碼如下所示：

上述代碼的時間復雜度仍然是O（n），但避免了多次重復掃描數(shù)組counts，和前面的解法相比時間效率有所提高。

面試題17：包含所有字符的最短字符串

分析：這又是一道關(guān)于統(tǒng)計子字符串中出現(xiàn)的字符及每個字符出現(xiàn)的次數(shù)的面試題。如果一個字符串s中包含另一個字符串t的所有字符，那么字符串t的所有字符在字符串s中都出現(xiàn)，并且同一個字符在字符串s中出現(xiàn)的次數(shù)不少于在字符串t中出現(xiàn)的次數(shù)。

有了前面的經(jīng)驗，就可以用一個哈希表來統(tǒng)計一個字符串中每個字符出現(xiàn)的次數(shù)。首先掃描字符串t，每掃描到一個字符，就把該字符在哈希表中對應的值加1。然后掃描字符串s，每掃描一個字符，就檢查哈希表中是否包含該字符。如果哈希表中沒有該字符，則說明該字符不是字符串t中的字符，可以忽略不計。如果哈希表中存在該字符，則把該字符在哈希表中的對應值減1。如果字符串s中包含字符串t的所有字符，那么哈希表中最終所有的值都應該小于或等于0。

仍然可以用兩個指針定位字符串s的子字符串，其中第1個指針指向子字符串的第1個字符，第2個指針指向子字符串的最后一個字符。

如果某一時刻兩個指針之間的子字符串還沒有包含字符串t的所有字符，則在子字符串中添加新的字符，于是向右移動第2個指針。如果仍然沒有包含字符串t的所有字符，則繼續(xù)向右移動第2個指針。

如果某一時刻兩個指針之間的子字符串已經(jīng)包含字符串t的所有字符，由于目標是找出最短的符合條件的子字符串，因此向右移動第1個指針，以判斷刪除子字符串最左邊的字符之后是否仍然包含字符串t的所有字符。

經(jīng)過分析可以發(fā)現(xiàn)，這里移動兩個指針的思路和面試題16的思路大同小異，感興趣的讀者請自行一步步仔細分析。該思路的參考代碼如下所示：

在上述代碼中，變量count是出現(xiàn)在字符串t中但還沒有出現(xiàn)在字符串s中的子字符串中的字符的個數(shù)。變量start相當于第1個指針，指向字符串s的子字符串中的第1個字符，變量end相當于第2個指針，指向字符串s的子字符串中的最后一個字符。當變量count等于0時，兩個指針之間的子字符串就包含字符串t中的所有字符。

這里哈希表使用了Java中的類型HashMap，而沒有和之前幾個題目一樣用數(shù)組模擬。這是因為用類型HashMap可以非常方便地判斷一個字符在字符串t中是否出現(xiàn)。如果一個字符在字符串t中出現(xiàn)，那么哈希表中一定包含該字符的鍵。

上述代碼中只有一個while循環(huán)，用來把兩個變量從0增加到字符串s的長度。如果字符串的長度是n，那么時間復雜度就是O（n）。可以使用一個哈希表來統(tǒng)計每個字符出現(xiàn)的次數(shù)。哈希表的鍵為字符，假設字符串中只有英文字母，那么哈希表的大小不會超過256，輔助空間的大小不會隨著字符串長度的增加而增加，因此空間復雜度是O（1）。