3.2 双指针

第2章用两个指针来定位一个子数组，其中一个指针指向数组的第1个数字，另一个指针指向数组的最后一个数字，那么两个指针之间所包含的就是一个子数组。

如果将字符串看成一个由字符组成的数组，那么也可以用两个指针来定位一个子字符串，其中一个指针指向字符串的第1个字符，另一个指针指向字符串的最后一个字符，两个指针之间所包含的就是一个子字符串。

可以在移动这两个指针的同时，统计两个指针之间的字符串中字符出现的次数，这样可以解决很多常见的面试题，如在一个字符串中定位另一个字符串的变位词等。

由于这种类型的面试题都与统计字母出现的次数有关，我们经常使用哈希表来存储每个元素出现的次数，因此解决这种类型的面试题通常需要同时使用双指针和哈希表。

面试题14：字符串中的变位词

分析：变位词是与字符串相关的面试题中经常出现的一个概念。所谓的变位词是指组成各个单词的字母及每个字母出现的次数完全相同，只是字母排列的顺序不同。例如，"pots"、"stop"和"tops"就是一组变位词。

由变位词的定义可知，变位词具有以下几个特点。首先，一组变位词的长度一定相同；其次，组成变位词的字母集合一定相同，并且每个字母出现的次数也相同。

这个题目如果不考虑时间复杂度，用暴力法就可以解决。实际上，一个字符串的变位词是字符串的排列。可以先求出字符串s1的所有排列，然后判断每个排列是不是字符串s2的子字符串。如果一个字符串有n个字符，那么它一共有n！（n的阶乘）个排列，因此这种解法的时间复杂度不会低于O（n！）。

下面尝试寻找更高效的算法。既然题目是关于变位词的，而变位词与字母及字母出现的次数有关，那么就应该统计字符串中包含的字母及每个字母出现的次数。如果一个哈希表的键是字母，而哈希表中的值是对应字母出现的次数，那么这样一个哈希表很适合用来统计字符串中每个字母出现的次数。

由于这个题目强调字符串中只包含英文小写字母，而英文小写字母的个数是确定的，一共26个，因此可以用数组模拟一个简单的哈希表。数组的下标0对应字母'a'，它的值对应字母'a'出现的次数。数组的下标1对应字母'b'，它的值对应字母'b'出现的次数。以此类推，数组的下标25对应字母'z'，它的值对应字母'z'出现的次数。

首先扫描字符串s1。每扫描到一个字符，就找到它在哈希表中的位置，并把它对应的值加1。如果字符串s1为"ac"，那么扫描该字符串并统计每个字母出现的次数之后的哈希表如图3.1（a）所示。在该哈希表中，只有字母'a'和字母'c'对应的值是1，其他值都是0，这是因为只有这两个字母在字符串中各出现了1次。

然后考虑如何判断字符串s2中是否包含字符串s1的变位词。假设字符串s2中有一个子字符串是字符串s1的变位词，逐个扫描这个变位词中的字母，并把字母在哈希表中对应的值减1。由于字符串s1的变位词和字符串s1包含相同的字母，并且每个字母出现的次数也相同，因此扫描完字符串s1的变位词之后，哈希表中所有的值都是0。

字符串s1的变位词和字符串s1的长度一样。假设字符串s1的长度是n，下面逐一判断字符串s2中长度为n的子字符串是不是字符串s1的变位词。判断的办法就是扫描子字符串中的每个字母，把该字母在哈希表中对应的值减1。如果哈希表中的所有值是0，那么该子字符串就是字符串s1的一个变位词。

下面以字符串"dgcaf"为s2作为例子来逐步分析这个过程。可以用双指针来定位一个子字符串，其中一个指针指向子字符串的第1个字符，另一个指针指向子字符串的最后一个字符。首先，双指针定位的子字符串为"dg"。如果扫描该子字符串中的两个字母'd'和'g'，那么在哈希表中把它们对应的值减1。此时哈希表的状态如图3.1（b）所示。

接下来把这两个指针都向右移动1位，让它们定位子字符串"gc"。每次移动这两个指针时都相当于在原来的子字符串的最右边添加一个新的字符，并且从原来子字符串中删除最左边的字符。每当在子字符串中添加一个字符时，就把哈希表中对应位置的值减1。同样，每当在子字符串中删除一个字符时，就把哈希表中对应位置的值加1。在把字母'c'的值减1、字母'd'的值加1之后，哈希表的状态如图3.1（c）所示。

再把两个指针都向右移动1位，让它们定位子字符串"ca"。这相当于在原来子字符串"gc"的最右边添加字母'a'，同时删除最左边的字母'g'。在把字母'a'的值减1、字母'g'的值加1之后，哈希表的状态如图3.1（d）所示。此时哈希表中所有的值都是0，因此这两个指针指向的子字符串就是字符串s1的一个变位词。

可以基于双指针和哈希表的思路编写如下所示的代码：

在上述函数checkInclusion中，第2个for循环中的下标i相当于第2个指针，指向子字符串的最后一个字符。第1个指针指向下标为i-s1.length()的位置。两个指针之间的子字符串的长度一直是字符串s1的长度。

上述基于双指针和哈希表的算法需要扫描字符串s1和s2各一次。如果它们的长度分别是m和n，那么该算法的时间复杂度是O（m+n）。这种解法用到了一个数组。数组的长度是英文小写字母的个数（即26），是一个常数，也就是说，数组的大小不会随着输入字符串长度的变化而变化，因此空间复杂度是O（1）。

面试题15：字符串中的所有变位词

分析：这个题目是面试题14的变种，所以也可以用一个哈希表来统计字符串s2中字母出现的次数。由于字母的总数是已知的，一共有26个英文小写字母，因此可以用一个长度为26的数组模拟一个哈希表。

如果字符串s2的长度为n，则逐个统计字符串s1中所有长度为n的子字符串中字母出现的次数。可以用两个指针来定位字符串s1的子字符串，第1个指针指向字符串的第1个字符，第2个指针指向字符串的最后一个字符。每次统计完子字符串中字符出现的次数之后，两个指针同时向右移动一位。两个指针每向右移动一位，相当于在上一次的子字符串的最右边加上一个字母，并删除原来子字符串最左边的字母。

每当在子字符串中添加一个字母，则把哈希表中该字母对应的值减1；每当从子字符串中删除一个字母，则把哈希表中该字母对应的值加1。如果哈希表中所有的值都是0，那么由两个指针定位的子字符串是字符串s2的一个变位词。按照题目要求，把第1个指针对应的下标添加到结果链表中。

由于这种思路和面试题14的思路基本一致，因此不再一步步分析。这种思路的参考代码如下所示：

辅助函数areAllZero和面试题14的代码中的一样，所以此处不再重复介绍。

同样，这种解法的时间复杂度也是O（n），空间复杂度是O（1）。

面试题16：不含重复字符的最长子字符串

分析：和前面的题目一样，此处还是用一个哈希表统计子字符串中字符出现的次数。如果一个子字符串中不含重复的字符，那么每个字符都只出现一次，它们在哈希表中对应的值为1。没有在子字符串中出现的其他字符对应的值都是0。也就是说，如果子字符串中不含重复字符，那么它对应的哈希表中没有比1大的值。

下面仍然用两个指针来定位一个子字符串，其中第1个指针指向子字符串的第1个字符，第2个指针指向子字符串的最后一个字符。接下来分析如何移动这两个指针。

如果两个指针之间的子字符串不包含重复的字符，由于目标是找出最长的子字符串，因此可以向右移动第2个指针，在子字符串的最右边增加新的字符，然后判断新的字符在子字符串中有没有重复出现。如果还是没有重复的字符，则继续向右移动第2个指针，在子字符串中添加新的字符。

例如，在字符串"babcca"中找最长的不含重复字符的子字符串时，两个指针都初始化指向第1个字符'b'，此时子字符串为"b"，不含重复字符（表3.2中的第1步）。于是向右移动第2个指针使其指向字符'a'，此时子字符串为"ba"，仍然不含重复字符（表3.2中的第2步）。于是再次向右移动第2个指针使其指向字符'b'。

如果两个指针之间的子字符串中包含重复的字符，则可以向右移动第1个指针，删除子字符串中最左边的字符。如果删除最左边的字符之后仍然包含重复的字符，则继续向右移动第1个指针删除最左边的字符。例如，表3.2中的第3步，两个指针之间的字符串是"bab"，有重复出现的字符，于是向右移动第1个指针使其指向字符'a'。

如果删除最左边的字符之后不再包含重复的字符，就可以向右移动第2个指针，在子字符串的右边添加新的字符。例如，表3.2中的第4步，此时两个指针之间的字符串是"ab"，没有重复出现的字符，于是向右移动第2个指针使其指向字符'c'，得到最长的不含重复字符的子字符串。

之后的步骤如表3.2所示，请读者自行一步步分析。

❖ 需要多次遍历整个哈希表的解法

在厘清上述思路之后，编写代码就会比较容易。参考代码如下所示：

由于这个题目没有说明字符串中只包含英文字母，那么就有可能包含数字或其他字符，因此字符就可能不止26个。假设字符串中只包含ASCII码的字符。由于ASCII码总共有256个字符，因此用来模拟哈希表的数组的长度就是256。

需要注意的是，每次调用函数hasGreaterThan1都可能需要扫描一次数组counts。虽然数组counts的长度是常数256，但扫描一次的时间是O（1），因此这个常数还是有点大。下面介绍避免多次遍历整个哈希表的解法。

❖ 避免多次遍历整个哈希表的解法

我们真正关心的是哈希表中有没有比1大的数字，因为如果有大于1的数字就说明子数组中包含重复的数字。可以定义一个变量countDup来存储哈希表中大于1的数字的个数，即子字符串中重复字符的个数。每次向右移动第2个指针使子字符串包含更多字符时都会把哈希表中对应的数字加1。当一个字符对应的数字从1变成2时，表示该字符重复出现了，因此变量countDup加1。

当向右移动第1个指针删除子字符串中最左边的字符时，都会把哈希表中对应的数字减1。当一个字符对应的数字由2变成1时，该字符不再重复出现，因此变量countDup减1。

根据这个优化思路编写的代码如下所示：

上述代码的时间复杂度仍然是O（n），但避免了多次重复扫描数组counts，和前面的解法相比时间效率有所提高。

面试题17：包含所有字符的最短字符串

分析：这又是一道关于统计子字符串中出现的字符及每个字符出现的次数的面试题。如果一个字符串s中包含另一个字符串t的所有字符，那么字符串t的所有字符在字符串s中都出现，并且同一个字符在字符串s中出现的次数不少于在字符串t中出现的次数。

有了前面的经验，就可以用一个哈希表来统计一个字符串中每个字符出现的次数。首先扫描字符串t，每扫描到一个字符，就把该字符在哈希表中对应的值加1。然后扫描字符串s，每扫描一个字符，就检查哈希表中是否包含该字符。如果哈希表中没有该字符，则说明该字符不是字符串t中的字符，可以忽略不计。如果哈希表中存在该字符，则把该字符在哈希表中的对应值减1。如果字符串s中包含字符串t的所有字符，那么哈希表中最终所有的值都应该小于或等于0。

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

如果某一时刻两个指针之间的子字符串还没有包含字符串t的所有字符，则在子字符串中添加新的字符，于是向右移动第2个指针。如果仍然没有包含字符串t的所有字符，则继续向右移动第2个指针。

如果某一时刻两个指针之间的子字符串已经包含字符串t的所有字符，由于目标是找出最短的符合条件的子字符串，因此向右移动第1个指针，以判断删除子字符串最左边的字符之后是否仍然包含字符串t的所有字符。

经过分析可以发现，这里移动两个指针的思路和面试题16的思路大同小异，感兴趣的读者请自行一步步仔细分析。该思路的参考代码如下所示：

在上述代码中，变量count是出现在字符串t中但还没有出现在字符串s中的子字符串中的字符的个数。变量start相当于第1个指针，指向字符串s的子字符串中的第1个字符，变量end相当于第2个指针，指向字符串s的子字符串中的最后一个字符。当变量count等于0时，两个指针之间的子字符串就包含字符串t中的所有字符。

这里哈希表使用了Java中的类型HashMap，而没有和之前几个题目一样用数组模拟。这是因为用类型HashMap可以非常方便地判断一个字符在字符串t中是否出现。如果一个字符在字符串t中出现，那么哈希表中一定包含该字符的键。

上述代码中只有一个while循环，用来把两个变量从0增加到字符串s的长度。如果字符串的长度是n，那么时间复杂度就是O（n）。可以使用一个哈希表来统计每个字符出现的次数。哈希表的键为字符，假设字符串中只有英文字母，那么哈希表的大小不会超过256，辅助空间的大小不会随着字符串长度的增加而增加，因此空间复杂度是O（1）。