分享｜单序列双指针

14 小时前

发布于河南

双指针 C C++Java Python3 算法和数据结构

单序列双指针

单序列双指针主要分为：反转字符串，相向双指针，同向双指针，背向双指针，原地修改，矩阵上的双指针。

核心思想

单序列双指针是一种通过在同一个数组或字符串上维护两个不同位置的指针，从而将 $O (n^{2})$ 的时间复杂度降低到 $O (n)$ 的高效技巧。

反转字符串

题目一

来源：力扣3794. 反转字符串前缀

给你一个字符串 s 和一个整数 k。

反转 s 的前 k 个字符，并返回结果字符串。

思路

设 $s$ 长度为 $n$ 。反转可以看成是交换 $s [0]$ 和 $s [k - 1]$ ，交换 $s [1]$ 和 $s [k - 2]$ ，交换 $s [2]$ 和 $s [k - 3]$ ，依此类推

初始化两个指针 $l e f t = 0$ 和 $r i g h t = k - 1$ 表示需要交换的位置。每次交换后，将指针向中间移动， $l e f t$ 加一， $r i g h t$ 减一。当 $l e f t \geq r i g h t$ 时，所有字符交换完毕，退出循环。

代码实现

Python

class Solution:
    def reversePrefix(self, s: str, k: int) -> str:
        s = list(s)
        l, r = 0, k - 1
        while l < r:
            s[l], s[r] = s[r], s[l]
            l, r = l + 1, r - 1

        return "".join(s)

题目二

来源：力扣3643. 垂直翻转子矩阵

给你一个 m x n 的整数矩阵 grid，以及三个整数 x、y 和 k。

整数 x 和 y 表示一个 正方形子矩阵 的左上角下标，整数 k 表示该正方形子矩阵的边长。

你的任务是垂直翻转子矩阵的行顺序。

返回更新后的矩阵。

思路

垂直翻转子矩阵.drawio.svg

如上图，假设 $5 X 5$ 的矩阵， $x = 1 ， y = 0 ， k = 4$ ，使用双指针，左指针 $l$ 初始指向第 $x$ 行，右指针 $r$ 指向第 $x + k - 1$ 行，然后左右指针行对应第 $y$ 到 $y + k - 1$ 个交换，交换结束之后，左指针向下一行，右指针向上一行，以此类推，直至相遇。

代码实现

Python

class Solution:
    def reverseSubmatrix(
        self, grid: List[List[int]], x: int, y: int, k: int
    ) -> List[List[int]]:
        l, r = x, x + k - 1
        while l < r:
            for j in range(y, y + k):
                grid[l][j], grid[r][j] = grid[r][j], grid[l][j]
            l += 1
            r -= 1

        return grid

题目三

来源：力扣3775. 反转元音数相同的单词

给你一个字符串 s，它由小写的英文单词组成，每个单词之间用一个空格隔开。

请确定 第一个单词 中的元音字母数。然后，对于每个 后续单词 ，如果它们的元音字母数与第一个单词相同，则将它们反转。其余单词保持不变。

返回处理后的结果字符串。

元音字母包括 'a', 'e', 'i', 'o' 和 'u'。

思路

涉及反转基本要使用双指针，遍历字符串直至遇到第一个空格，统计该区间内元音字母的数量，记为 $x$ 。若无空格，说明不存在后续单词，直接返回。初始化指针 $l e f t$ 指向第一个空格后的字符，表示当前待处理单词的起点。使用指针 $i$ 从 $l e f t$ 开始向后扫描。在扫描过程中，统计当前单词内的元音数量 $c n t$ 。当 $i$ 到达空格或字符串末尾 $n$ 时，确定了一个完整单词的边界。

若当前单词的元音数 $c n t$ 等于基准值 $x$ ，则令 $r i g h t = i - 1$ 。
执行交换：交换 $s [l e f t]$ 和 $s [r i g h t]$ ，随后 $l e f t$ 加一， $r i g h t$ 减一，直至 $l e f t >= r i g h t$ ，完成该单词的原地反转。

指针重置：将 $l e f t$ 更新为 $i + 1$ （跳过空格），重置 $c n t$ 为 $0$ ，继续寻找下一个单词，依此类推。

Python可以先把字符串根据空格拆分成多个单词，然后就转化成每个字符串的简单反转，最后再拼接到一起

代码实现

Cpp

class Solution {
public:
    int isAeiou(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }

    string reverseWords(string s) {
        int x = 0, n = s.size();
        int l = 0, r = 0;
        for (int i = 0; i < n; ++i) {
            char c = s[i];
            if (c == ' ') {
                l = i + 1;
                break;
            }
            if (isAeiou(c)) {
                x++;
            }
            if (i == n - 1) {
                return s;
            }
        }

        int cnt = 0;
        for (int i = l; i <= n; ++i) {
            char c = s[i];
            if (isAeiou(c)) {
                cnt++;
            }
            if (i == n || c == ' ') {
                if (cnt == x) {
                    r = i - 1;
                    while (l < r) {
                        swap(s[l], s[r]);
                        l++, r--;
                    }
                }
                l = i + 1;
                cnt = 0;
            }
        }

        return s;
    }
};

Python

class Solution:
    def reverseWords(self, s: str) -> str:
        def count_aeiou(s):
            return sum(c in "aeiou" for c in s)

        a = s.split()
        x = count_aeiou(a[0])

        for i in range(1, len(a)):
            if count_aeiou(a[i]) == x:
                a[i] = a[i][::-1]

        return " ".join(a)

相向双指针

两个指针 $l e f t = 0$ , $r i g h t = n - 1$ ，从数组的两端开始，向中间移动，这叫相向双指针。

不一定是从两端，区间内向中间移动即可，之前学的反转字符串大部分都是相向双指针。反转字符串是指针移动时做交换操作，本节还会学习其他操作，比如对称比较，利用单调性缩小搜索空间，元素过滤等

题目一

来源：力扣125. 验证回文串

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

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

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

思路

经典的双指针判断回文串，左指针初始指向 $0$ ，右指针初始指向 $l e n (s) - 1$ ，左指针向右找到字母数字字符，然后右指针也向左找字母数字字符，注意指针移动过程中要时刻满足，左指针小于右指针，都找到之后，转换为小写字符判断是否相同即可，不相同则直接返回 $f a l se$ ，相同则继续向后找，直至指针相遇，返回 $t r u e$ 。

代码实现

Python

class Solution:
    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1
        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            while l < r and not s[r].isalnum():
                r -= 1

            if s[l].lower() != s[r].lower():
                return False

            l, r = l + 1, r - 1

        return True

题目二

来源：力扣658. 找到 K 个最接近的元素

给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足：

|a - x| < |b - x| 或者

|a - x| == |b - x| 且 a < b

思路

已知数组是有序的，数组中找到最靠近 $x$ 的 $k$ 个数必定是在一个连续区间里，我们可以用相向双指针，左右指针分别指向两端，那边更不符合条件（离 $x$ 远，距离相同则值大的不符合），就移动哪边指针，排除出更不符合要求的元素，直至数组剩余 $k$ 个元素，一定是最符合要求的 $k$ 个。

代码实现

Python

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        l, r = 0, len(arr) - 1
        while r - l + 1 > k:
            if x - arr[l] <= arr[r] - x:
                r -= 1
            else:
                l += 1

        return arr[l : r + 1]

题目三

来源：力扣948. 令牌放置

你的初始能量为 power，初始分数为 0，只有一包令牌以整数数组 tokens 给出。其中 tokens[i] 是第 i 个令牌的值（下标从 0 开始）。

你的目标是通过有策略地使用这些令牌以 最大化 总分数。在一次行动中，你可以用两种方式中的一种来使用一个 未被使用的 令牌（但不是对同一个令牌使用两种方式）：

朝上：如果你当前至少有 tokens[i] 点能量，可以使用令牌 i ，失去 tokens[i] 点能量，并得到 1 分。

朝下：如果你当前至少有 1 分，可以使用令牌 i ，获得 tokens[i] 点能量，并失去 1 分。

在使用任意数量的令牌后，返回我们可以得到的最大分数。

思路

如果让我们来玩令牌放置这个游戏，在让令牌正面朝上的时候，肯定要去找能量最小的令牌。同样的，在让令牌反面朝上的时候，肯定要去找能量最大的令牌。

只要还有能量，就一直让令牌正面朝上，直到没有能量的时候，让一个令牌反面朝上从而获得能量继续之前的操作。

最终答案一定是在一次让令牌正常朝上操作之后产生的（永远不可能在让令牌反面朝上操作之后产生）

可以排序后使用双指针，左指针指向未使用的能量最小的令牌，右指针指向未使用的能量最大的令牌。只要能量够用，就一直让左指针令牌正面朝上，右移左指针，能量不够就让右指针令牌反面朝上，左移右指针。

注意：每次操作前，左右指针都是指向的未使用的令牌，所以左右指针指向同一个也是可以的。

代码实现

Python

class Solution:
    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
        tokens.sort()
        l, r, ans, res = 0, len(tokens) - 1, 0, 0
        while l <= r:
            if power >= tokens[l]:
                power -= tokens[l]
                l, res = l + 1, res + 1
                ans = max(ans, res)
            elif ans > 0:
                power += tokens[r]
                r, res = r - 1, res - 1
            else:
                break

        return ans

题目四

来源：力扣42. 接雨水相向双指针中逻辑最精妙的题目之一

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

思路

注意到下标 $i$ 处能接的雨水量由 $l e f tM a x [i]$ 和 $r i g h tM a x [i]$ 中的最小值决定。由于数组 $l e f tM a x$ 是从左往右计算，数组 $r i g h tM a x$ 是从右往左计算，因此可以使用双指针和两个变量代替两个数组。

维护两个指针 $l e f t$ 和 $r i g h t$ ，以及两个变量 $l e f tM a x$ 和 $r i g h tM a x$ ，初始时 $l e f t = 0, r i g h t = n - 1, l e f tM a x = 0, r i g h tM a x = 0$ 。指针 $l e f t$ 只会向右移动，指针 $r i g h t$ 只会向左移动，在移动指针的过程中维护两个变量 $l e f tM a x$ 和 $r i g h tM a x$ 的值。

当两个指针没有相遇时，进行如下操作：

使用 $h e i g h t [l e f t]$ 和 $h e i g h t [r i g h t]$ 的值更新 $l e f tM a x$ 和 $r i g h tM a x$ 的值；
哪边低，哪边就能确定水量，因为较低的一边水位是由其对应的 $ma x$ 决定的，而另一边肯定有更高的墙（木桶效应：如果 $h e i g h t [l] < h e i g h t [r]$ ，那么对于 $l$ 这个位置来说，它右边至少有一个 $h e i g h t [r]$ 挡着，所以它的水位上限只取决于左边的最高点 $l e f tM a x$ 。）

当两个指针相遇时，即可得到能接的雨水总量。

代码实现

Python

class Solution:
    def trap(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        l_max = r_max = ans = 0

        while l < r:
            l_max = max(l_max, height[l])
            r_max = max(r_max, height[r])

            if height[l] < height[r]:
                ans += l_max - height[l]
                l += 1
            else:
                ans += r_max - height[r]
                r -= 1

        return ans

同向双指针

两个指针的移动方向相同（都向右，或者都向左）。滑动窗口也相当于同向双指针。

题目一

来源：力扣2200. 找出数组中的所有 K 近邻下标

给你一个下标从 0 开始的整数数组 nums 和两个整数 key 和 k 。K 近邻下标 是 nums 中的一个下标 i ，并满足至少存在一个下标 j 使得 |i - j| <= k 且 nums[j] == key 。

以列表形式返回按 递增顺序 排序的所有 K 近邻下标。

思路

枚举 $k ey$ 的位置，去把邻近的 $i$ 加入答案。

具体来说，遍历 $n u m s$ ，如果 $n u m s [i] = k ey$ ，那么 $[ma x (i - k, 0), min (i + k, n - 1)]$ 中的下标可以在答案中

同向双指针思维，左右指针初始都指向 $0$ 遍历 $n u m s$ ，如果 $n u m s [i] = k ey$ ，左指针更新指向 $ma x (i - k, 0)$ ，右指针更新指向 $min (i + k, n - 1)$ ，将这些下标加入答案数组中。

代码实现

Python

class Solution:
    def findKDistantIndices(self, nums: List[int], key: int, k: int) -> List[int]:
        ans, l = [], 0
        for i, x in enumerate(nums):
            if x == key:
                l = max(i - k, l)
                r = min(i + k, len(nums) - 1)
                ans.extend(range(l, r + 1))
                l = r + 1

        return ans

题目二

来源：力扣611. 有效三角形的个数

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

思路

判断三条线段能否组成一个三角形，主要遵循以下核心准则。假设三角形的三条边长度分别为 $a$ ， $b$ 和 $c$ ，

则必须满足三角形两边之和大于第三边，即：

a + b > c a + c > b b + c > a

由于我们不能重复统计，那么不妨规定三角形的三条边 $a, b, c$ 满足：

1 \leq a \leq b \leq c

这可以保证我们在统计合法三元组 $(a, b, c)$ 的个数时，不会把 $(c, b, a)$ 这样的三元组也统计进去。

由于 $1 \leq a \leq b \leq c$ ，上式中的 $a + c > b$ 是必然成立的，因为 $a + c \geq a + b > b$ （注意 $a$ 至少是 $1$ ）。同样的， $b + c > a$ 也必然成立，因为 $b + c \geq a + a > a$ （注意 $a$ 至少是 $1$ ）。

所以只需考虑第一个式子。现在问题变成：从 $n u m s$ 中选三个数 $a, b, c$ ，计算满足 $1 \leq a \leq b \leq c$ 且 $a + b > c$ 的方案数。

为了能够使用相向双指针，先对数组从小到大排序。外层循环枚举最长边 $c = n u m s [k]$ ，内层循环用相向双指针枚举 $a = n u m s [i]$ 和 $b = n u m s [j]$ 。

代码实现

Python

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        ans, n = 0, len(nums)
        for i in range(n - 1, 1, -1):
            l, r = 0, i - 1
            while l < r:
                if nums[l] + nums[r] > nums[i]:
                    ans += r - l
                    r -= 1
                else:
                    l += 1

        return ans

题目三

来源：力扣3649. 完美对的数目

给你一个整数数组 nums。

如果一对下标 (i, j) 满足以下条件，则称其为完美的：

i < j

令a = nums[i]，b = nums[j]。那么：

min(|a - b|, |a + b|) <= min(|a|, |b|)

max(|a - b|, |a + b|) >= max(|a|, |b|)

返回不同完美对的数量。

**注意：**绝对值 |x| 指的是 x 的非负值。

思路

由于部分数学证明，后续补充题解，此处说明本题有学习意义

背向双指针

两个指针从数组中的同一个位置出发，一个向左，另一个向右，背向移动。

题目一

来源：力扣658. 找到 K 个最接近的元素

给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足：

|a - x| < |b - x| 或者

|a - x| == |b - x| 且 a < b

思路

之前学习了相向双指针的思路，本题还可以使用背向双指针。

已知数组是有序的，数组中找到最靠近 $x$ 的 $k$ 个数必定是在一个连续区间里，我们可以用背向双指针。

假设数组长度为 $n$ ，注意到数组 $a rr$ 已经按照升序排序，我们可以将数组 $a rr$ 分成两部分，前一部分所有元素 $[0, l e f t]$ 都小于 $x$ ，后一部分所有元素 $[r i g h t, n - 1]$ 都大于等于 $x$ ， $l e f t$ 与 $r i g h t$ 都可以通过二分查找获得。

$l e f t$ 和 $r i g h t$ 指向的元素都是各自部分最接近 $x$ 的元素，因此我们可以通过比较 $l e f t$ 和 $r i g h t$ 指向的元素获取整体最接近 $x$ 的元素。如果 $x - a rr [l e f t] \leq a rr [r i g h t] - x$ ，那么将 $l e f t$ 减一，否则将 $r i g h t$ 加一。相应地，如果 $l e f t$ 或 $r i g h t$ 已经越界，那么不考虑对应部分的元素。

最后， $k$ 次操作之后，区间 $[l e f t + 1, r i g h t - 1]$ 的元素就是我们所要获得的结果。

代码实现

Python

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        right = bisect_left(arr, x)
        left = right - 1
        for _ in range(k):
            if left < 0:
                right += 1
            elif right >= len(arr) or x - arr[left] <= arr[right] - x:
                left -= 1
            else:
                right += 1
                
        return arr[left + 1: right]

题目二

来源：力扣1793. 好子数组的最大分数

给你一个整数数组 nums **（下标从 0 开始）**和一个整数 k 。

一个子数组 (i, j) 的分数定义为 min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 。一个好子数组的两个端点下标需要满足 i <= k <= j 。

请你返回好子数组的最大可能分数。

思路

例如 $n u m s = [1, 9, 7, 8, 8, 1], k = 3 。$

其中面积最大的矩形，左边界下标 $L = 1$ ，右边界下标 $R = 4$ 。

我们尝试从 $i = k, j = k$ 出发，通过不断移动指针来找到最大矩形。

比较 $x = n u m s [i - 1]$ 和 $y = n u m s [j + 1]$ 的大小，谁大就移动谁（一样大移动哪个都可以），让最小值减少得更慢。

代码实现

Python

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        n = len(nums)
        ans = min_h = nums[k]
        i = j = k
        for _ in range(n - 1):
            if j == n - 1 or i and nums[i - 1] > nums[j + 1]:
                i -= 1
                min_h = min(min_h, nums[i])
            else:
                j += 1
                min_h = min(min_h, nums[j])
                
            ans = max(ans, min_h * (j - i + 1))
            
        return ans

原地修改

题目一

来源：力扣27. 移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。

返回 k。

思路

经典的原地修改题，双指针解法，左右指针初始均指向 0，右指针遍历数组，当右指针指向的值不为 val 时，修改左指针指向的值为右指针指向的值（相当于重新排列数组，跳过值为 val 的元素），左指针右移，最后返回左指针。

代码实现

Python

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        l = 0
        for r in nums:
            if r != val:
                nums[l] = r
                l += 1

        return l

矩阵上的双指针

后续补充。