在关于数组的问题中,有那么一类问题,它们可以利用双指针(Two Pointers)方法解决。需要说明的一点是,这里提到的“指针”不一定指的是严格意义上的指针,在很多场合下,它被用来代指用来进行遍历的下标i
或j
。所以“双指针”问题其实就是利用两个下标i
和j
对数组进行遍历的一类问题。本文就来列举一部分面试中经常涉及到的“双指针”问题。
类别一
1、Two Sum问题
问题:输入一个排好序的int
类型数组arr
,以及一个整数target
。判断arr
中是否存在两个元素,它们的和等于target
。
解法:这个问题是双指针问题中比较基础并且比较典型的一类问题了。我们定义两个指针i
和j
,分别从数组的左右端点开始遍历,在遍历时,观察arr[i]
和arr[j]
的和sum
。如果sum > target
,则j--
;如果sum < target
,则i++
。如果i
和j
已经相遇但是仍未找到答案,则说明原数组不存在这样的两个元素。
分析:相比起O(n2)
的暴力解法,双指针的方法进行了剪枝,将时间复杂度减少到了O(n)
。
2、判断一个字符串是否是回文字符串
问题:输入一个字符串str
,判断它是不是回文字符串。
解法:仍然是定义两个指针i
和j
,分别从字符串的左右端点开始遍历。在每个迭代中,观察str[i]
和str[j]
是否相等,并且令i
右移一格、j
左移一格,直到两个指针相遇。
分析:同类的题目还有在O(n)
时间内原地反转字符串等。
3、容积最大的容器
问题:Given n
non-negative integers a1
, a2
, …, an
, where each represents a point at coordinate (i, ai)
. n
vertical lines are drawn such that the two endpoints of line i
is at (i, ai)
and (i, 0)
. Find two lines, which together with x-axis forms a container, such that the container contains the most water. Note: You may not slant the container.
解法:暴力解法的时间复杂度为O(n2)
,能不能像前面提到的Two Sum问题一样进行剪枝呢?答案是肯定的。
我们在遍历的过程中用maxWater
记录当前最大的容积。假设容器的两条边是0
和n-1
号,我们可以算出一个容量F(0,n-1) = height[0] * (n-1)
,将其作为maxWater
的初始值。
我们注意到:如果0
号边的高度不大于n-1
号边的高度,所有以0
号边为左侧边的容器容积都比F(0,n-1)
小。因为所有这样的容器高度肯定不大于height[0]
,但是宽度却一定小于n-1
,所以其容积肯定小于F(0,n-1)
,所以我们不需要对这些情况进行枚举。同理,如果0
号边的高度大于n-1
号边的高度,我们就不需要对其他以n-1
号边作为右侧边的容器进行枚举了。
这样我们就完成了剪枝。我们定义两个指针i
和j
,分别从数组的左右端点开始遍历。每个迭代,先算出F(i,j)
并更新maxWater
的值,然后根据前面得出的结论:如果height[i]
不大于height[j]
,直接i++
;否则直接j--
。显然,这种方法的时间复杂度是O(n)
。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
总结
这一类的双指针问题有一个共同之处:分别从数组的左右端点开始遍历。其中,问题二需要这样做,是因为需要研究字符串本身的对称性;问题一和问题三需要这样做,是对暴力搜索进行剪枝的结果。
类别二
1、删除数组中所有值等于val
的元素
问题:Given an array and a value, remove all instances of that value in place and return the new length. Note: The order of elements can be changed. It doesn’t matter what you leave beyond the new length.
解法:通常我们会使用一个新的数组来存储那些不被删除的数,这样就能够很顺利的完成任务。但是实际上由于在这个过程中,新数组的大小是肯定会小于原本数组中已经处理过的数的数量的,所以我们就可以直接利用原本数组中已经处理过的数的位置,避免再开一个额外的数组。所以这里就用到了一种思想,定义两个指针i
和cnt
,i
是遍历用的指针,cnt
指向新数组的下一个位置。每当i
遍历到一个符合条件的元素,就通过arr[cnt++] = arr[i]
将其加入到新数组中。此方法的时间复杂度是O(n)
。
1 2 3 4 5 6 7 8 9 |
|
2、奇偶分类
问题:输入一个数组,将其进行重排,使得所有奇数位于所有偶数的前面。
解法:我们定义两个指针i
和j
,其中j
是遍历用的指针,i
则记录了当前数组奇数部分的下一个位置。每当j
遍历到一个奇数时,就交换arr[i]
和arr[j]
的值,然后i++
。这样当数组遍历完毕后,arr[0..i-1]
就存储了所有的奇数,剩下的部分则存储了所有的偶数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
3、替换空格
问题:实现一个函数,把字符串中的每个空格都替换成"%20"
。
解法:如果是暴力解法,从前往后遍历字符串,在遍历到空格的时候,就将后面的所有字符后移两格,这样的方法在最坏情况下(字符串中都是空格)是O(n2)
的。我们有更快的解法,其时间复杂度为O(n)
,每个字符只需要向后移动一次,那就是“从后往前替换字符串”。
首先遍历一遍原字符串确认有多少个空格,这样我们就得到了新字符串的长度。然后我们令p1
从原字符串的末尾往前遍历,p2
指向新字符串中已经被替换好的部分的前一个元素。如果arr[p1]
不是空格,直接将其拷贝到arr[p2]
的位置,然后p2
左移一格;如果arr[p1]
是空格,则在p2
位置依次插入0
、2
和%
。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
总结
这一类的双指针问题有一个共同之处:其中一个指针用于遍历,另一个指针指向数组已完成部分的下一个元素。这种方法可以节省空间,或者减少数据重复移动的次数。
类别三
1、无重复字符的最长子字符串
问题:Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb"
is "abc"
, which the length is 3. For "bbbbb"
the longest substring is "b"
, with the length of 1.
解法:利用p1
和p2
两个指针构成一个窗口,其中p1
指向窗口的第一个元素,p2
指向窗口最后一个元素的下一个元素。我们利用一个hashmap记录窗口中各个字符的出现次数,并且保证窗口中没有重复字符。
具体做法是:观察即将加入窗口中的字符str[p2]
。如果该字符没有在窗口中出现过,我们可以直接将该字符加入窗口中,即p2++
,同时调整hashmap的记录;如果该字符在窗口中出现过,那么我们令p1++
来缩小窗口的大小,同时调整hashmap的记录,直到该字符没有在窗口中出现为止。在遍历的过程中,记录窗口达到的最大长度。算法的时间复杂度为O(n)
。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|
2、Minimum Window Substring
问题:Given a string S
and a string T
, find the minimum window in S
which will contain all the characters in T
in complexity O(n)
. For example,
S = “ADOBECODEBANC”
T = “ABC”
Minimum window is "BANC"
.
Note: If there is no such window in S
that covers all characters in T
, return the empty string ""
. If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S
.
解法:我们仍然利用两个指针p1
和p2
组成一个窗口,其中p1
指向窗口的第一个元素,p2
指向窗口最后一个元素的下一个元素。我们还要定义一个哈希表set
,表示T
中出现过哪些字符,如果遍历到没有在T
中出现过的字符,我们可以将该字符跳过,继续遍历下一个字符。
为了记录窗口中的字符和T
中字符的匹配情况,我们定义一个整数count
,表示T
中待匹配的字符数量,count
等于0
说明T
中所有字符都已经匹配上;另外,定义一个哈希表num
,表示每个字符的待匹配次数,比如当num['a']
等于2
时,说明窗口中还要再包括进两个'a'
才能满足题意。需要注意的是,num
中字符对应的待匹配次数可以为负,负数说明该字符过匹配(出现次数太多了)。
在每次遍历中,我们首先检查count
是否大于0
。
如果count
大于0
,说明还有字符待匹配,我们需要将s[p2]
加入到窗口中,并且令num[s[p2]]--
。如果该字符还没有过匹配(num[s[p2]]>=0
),那么将该字符加入窗口后,待匹配的字符数量减少1
,所以count--
;如果s[p2]
过匹配(num[s[p2]]<0
),那么将该字符加入窗口后并不能使待匹配的字符数量减少,所以count
不发生变化。
如果count
等于0
,说明已经找到了一个符合题意的窗口,我们需要将记录当前窗口的长度,然后继续向下搜索:从窗口中取出s[p1]
,并且令num[s[p1]]++
。如果发现num[s[p1]]>0
,说明该字符从匹配状态变成了未匹配状态,所以待匹配的字符数量增加1
,即count++
;如果发现num[s[p1]]<=0
,说明该字符仍是匹配状态,待匹配的字符数量并没有增加,所以count
不发生变化。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
|
总结
这一类的双指针问题主要是利用两个指针构造一个窗口,然后对窗口的内容进行讨论。