【数据结构和算法】：双指针

飞熊 • 2024年1月14日下午9:42 • 技术随笔 • 阅读 302

本文，我们将探讨双指针技巧，它可以帮助我们解决许多与数组/字符串相关的问题。

⭐️双指针⭐️

🌍使用情景一
🌍使用情景二

🌍使用情景一

在之前的学习中，我们通过迭代数组来解决一些问题。通常，我们只需要一个指针进行迭代，即从数组中的第一个元素开始，最后一个元素结束。可是有些时候我们使用两个指针进行迭代去解决某些题目会更加的方便。

参考代码：

public void reverseString(char[] s) {
    int n = s.length;
    for (int left = 0, right = n - 1; left < right; ++left, --right) {
        char tmp = s[left];
        s[left] = s[right];
        s[right] = tmp;
    }
}

我们先从经典例题入手：
编写一个函数，其作用是将输入的字符串反转过来。

思路与算法:官方解答

对于长度为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，反转结束，返回字符数组即可。

class Solution {
    public void reverseString(char[] s) {
        int n = s.length;
        for (int left = 0, right = n - 1; left < right; ++left, --right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
        }
    }
}

🌍使用情景二

转载自：双指针技巧 —— 情景二
有时，我们可以使用两个不同步的指针来解决问题，即快慢指针。与情景一不同的是，两个指针的运动方向是相同的，而非相反。
让我们从一个经典问题开始：

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

如果我们没有空间复杂度上的限制，那就更容易了。我们可以初始化一个新的数组来存储答案。如果元素不等于给定的目标值，则迭代原始数组并将元素添加到新的数组中。

实际上，它相当于使用了两个指针，一个用于原始数组的迭代，另一个总是指向新数组的最后一个位置。
考虑空间限制

如果我们不使用额外的数组，只是在原数组上进行操作呢？

此时，我们就可以采用快慢指针的思想：初始化一个快指针 fast 和一个慢指针 slow，fast 每次移动一步，而 slow 只当fast指向的值不等于 val 时才移动一步。

例题：

参考代码：

class Solution {
    public int removeElement(int[] nums, int val) {

        // 快慢指针
        int fastIndex = 0;
        int slowIndex;
        for (slowIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;

    }
}