Skip to content

Lesson9 字符串双指针算法专题

双指针（Two Pointers）：指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。如果两个指针方向相反，则称为「对撞指针」。如果两个指针方向相同，则称为「快慢指针」。如果两个指针分别属于不同的数组 / 链表，则称为「分离双指针」；本章仅针对字符串对撞指针进行介绍和题目分析。

1 对撞指针

对撞指针：指的是两个指针left、right分别指向序列第一个元素和最后一个元素，然后left指针不断递增，right不断递减，直到两个指针的值相撞（即 left== right），或者满足其他要求的特殊条件为止。

对撞指针

1.1 对撞指针解题步骤

  1. 使用两个指针left，right。left指向序列第一个元素，即：left=0，right指向序列最后一个元素，即：right=len(nums)-1。
  2. 在循环体中将左右指针相向移动，当满足一定条件时，将左指针右移，left+=1。当满足另外一定条件时，将右指针左移，right-=1。
  3. 直到两指针相撞（即 left==right），或者满足其他要求的特殊条件时，跳出循环体。

1.2 对撞指针伪代码模版

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
left, right = 0, len(nums) - 1

while left < right:
    if 满足要求的特殊条件:
        return 符合条件的值 
    elif 一定条件 1:
        left += 1
    elif 一定条件 2:
        right -= 1

return 没找到 或 找到对应值

1.3 对撞指针适用范围

对撞指针一般用来解决有序数组或者字符串问题：

  • 查找有序数组中满足某些约束条件的一组元素问题：比如二分查找、数字之和等问题。
  • 字符串反转问题：反转字符串、回文数、颠倒二进制等问题。

2 例题讲解

2.1 LC 344 反转字符串

问题描述

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

思路分析

对于长度为 N 的待被反转的字符数组，我们可以观察反转前后下标的变化，假设反转前字符数组为 s[0] s[1] s[2] ... s[N - 1]，那么反转后字符数组为 s[N - 1] s[N - 2] ... s[0]。比较反转前后下标变化很容易得出 s[i] 的字符与 s[N - 1 - i] 的字符发生了交换的规律，因此我们可以得出如下双指针的解法：

  • 将 left 指向字符数组首元素，right 指向字符数组尾元素。
  • 当 left < right：
    • 交换 s[left] 和 s[right]；
    • left 指针右移一位，即 left = left + 1；
    • right 指针左移一位，即 right = right - 1。
  • 当 left >= right，反转结束，返回字符数组即可。

提示

  • 字符数组是可变的，但你不能使用额外的数组空间，因此需要在原地修改字符顺序。

参考解答1

Python
1
2
3
4
5
class Solution(object):
    def reverseString(self, s):
        for i in range(len(s)//2):
            s[i],s[-1-i] = s[-1-i],s[i]
        return s

参考解答2

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution(object):
    def reverseString(self, s):
        i = 0
        j = len(s) -1
        while i < j:
            temp = s[i]
            s[i] = s[j]
            s[j] = temp
            i += 1
            j -= 1
        return s

调用函数法

Python
1
2
3
class Solution(object):
    def reverseString(self, s):
        return s.reverse()

2.2 LC 125 验证回文串

问题描述

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

提示

  • 需要忽略字符串中的空格、标点符号等非字母数字字符，并且在判断回文时不区分大小写。
  • 可以使用双指针从两端向中间移动，逐字符检查是否相等。

思路分析

最简单的方法是对字符串 s 进行一次遍历，并将其中的字母和数字字符进行保留，放在另一个字符串 sgood 中。这样我们只需要判断 sgood 是否是一个普通的回文串即可。使用双指针，从字符串的两端向中间遍历，逐个比较对应字符。

参考解答

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution(object):
    def isPalindrome(self, s):
        i, j = 0, len(s)-1
        while i < j:
            while i < j and not s[i].isalnum():
                i += 1
            while i < j and not s[j].isalnum():
                j -= 1
            if s[i].lower() != s[j].lower():
                return False
            i += 1
            j -= 1
        return True

切片法

Python
1
2
3
4
class Solution(object):
    def isPalindrome(self, s):
        sgood = "".join(ch.lower() for ch in s if ch.isalnum())
        return sgood == sgood[::-1]

3 举一反三

3.1 LC 345 反转字符串中的元音字母

问题描述

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。

元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现不止一次。

提示

  • 你需要在原地反转字符串中的元音字母，同时保持其他字符的位置不变。
  • 注意处理大小写不敏感的元音字符。

思路分析

我们可以使用两个指针 l 和 r 对字符串相向地进行遍历。

  • 指针 l初始时指向字符串 s 的首位，指针 r 初始时指向字符串 s 的末位。
  • 在遍历的过程中，不停地将 l 向右移动，直到 l 指向一个元音字母（或者超出字符串的边界范围）；同时，不停地将 r 向左移动，直到 r 指向一个元音字母。
  • 此时，如果 l < r，那么交换 l 和 r 指向的元音字母，否则说明所有的元音字母均已遍历过，就可以退出遍历的过程。

参考解答

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution(object):
    def reverseVowels(self, s):
        chars = list(s)
        l, r = 0, len(s) - 1
        vowels = set('aeiouAEIOU')

        while l < r:
            while l < len(s) and chars[l] not in vowels:
                l += 1
            while r >= 0 and chars[r] not in vowels:
                r -= 1
            if l >= r:
                break
            chars[l], chars[r] = chars[r],chars[l]
            l += 1
            r -= 1
        return "".join(chars)

3.2 LC 917 仅仅反转字母

问题描述

给你一个字符串 s ，根据下述规则反转字符串：

  • 所有非英文字母保留在原有位置。
  • 所有英文字母（小写或大写）位置反转。

返回反转后的 s 。

提示

  • 只需要反转字母，其他字符保持不变。
  • 可以使用双指针法来遍历和交换字母。

思路分析

使用双指针法：

  • l 指针从左向右遍历，寻找第一个字母；
  • r 指针从右向左遍历，寻找最后一个字母；
  • 交换这两个字母并移动指针，直到 l 和 r 相遇。

参考示例

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution(object):
    def reverseOnlyLetters(self, s):
        l,r = 0, len(s) - 1
        slist = list(s)
        while l < r:
            while l < r and not s[l].isalpha():
                l += 1
            while l < r and not s[r].isalpha():
                r -= 1
            slist[l], slist[r] = slist[r], slist[l]
            l += 1
            r -= 1
        return "".join(slist)

3.3 LC 680 验证回文串 II

问题描述

给你一个字符串 s，最多 可以从中删除一个字符。

请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

提示

  • 需要考虑最多删除一个字符后字符串是否可以成为回文。
  • 可以使用双指针法，遇到不匹配时尝试删除左边或右边的一个字符。

思路分析

首先进行回文串的验证，如果发现不匹配的字符，尝试跳过一个字符并继续验证。具体方法是：

  • 使用双指针，分别从字符串两端向中间遍历。
  • 一旦发现两个字符不匹配，可以尝试删除左边或右边的一个字符，再判断删除后的字符串是否为回文串。

参考解答

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution(object):
    def validPalindrome(self, s):
        if s == s[::-1]:
            return True
        l, r = 0, len(s)-1
        while l < r:
            if s[l] == s[r]:
                l += 1
                r -= 1
            else:
                 # 尝试删除左边或右边的字符后检查是否是回文
                return s[l+1:r+1] == s[l+1:r+1][::-1] or s[l:r] == s[l:r][::-1]
        return True

课后练习

题目编号 题目名称 主要考点
151 反转字符串中的单词 字符串反转，空格处理
392 判断子序列 子序列判断，双指针
541 反转字符串 II 分段字符串反转，迭代处理
1332 删除回文子序列 回文判断，字符串删除