双指针进阶：原地去重、合并数组与有序数组的平方

前面已经接触过一些双指针的基础题目，这次继续通过三道 LeetCode 题目，练习快慢指针和左右指针的不同用法。

虽然都属于双指针，但具体实现时，需要根据题目要求确定指针的含义。例如，慢指针可以指向最后一个有效元素，也可以指向下一个写入位置；有时为了避免覆盖尚未处理的数据，还需要改变遍历方向，从数组末尾开始操作。

1. LeetCode 80. 删除有序数组中的重复项 II

这道题可以看作 LeetCode 26. 删除有序数组中的重复项 的进阶版本。

第 26 题要求每个元素只保留一次，而这道题允许每个元素最多出现两次。

先回顾一下第 26 题的快慢指针思路：

• slow 指向已经保留的有效区间末尾。
• fast 向后遍历，寻找不同的元素。
• 遇到新元素时，将 slow 加一，再把新元素写入对应位置。

最终 [0, slow] 就是去重后的有效区间，因此返回 slow + 1。

不过，这道题允许保留两个相同的元素，直接跳过所有重复项显然不合适。

1.1 使用 count 统计出现次数

最容易想到的方法，就是在原来的快慢指针基础上，增加一个 count 变量，记录当前数字已经被扫描了多少次。

遍历过程中：

1. 如果 fast 和 slow 指向的值不同，说明遇到了新元素，直接保留。
2. 如果两者相同，就检查 count 是否小于 2，只有尚未超过允许数量时才保留。
3. 每次扫描完一个元素后，将 count 加一。
4. 如果下一个元素与当前元素不同，就将 count 清零，开始统计新的数字。

这里还需要判断 slow < fast，避免两个指针重合时，把当前位置重复计入有效区间。

Python 代码：

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow = 0
        fast = 0
        count = 0
        while fast < len(nums):
            if nums[fast] != nums[slow]:
                slow += 1
                nums[slow] = nums[fast]
            elif slow < fast and count < 2:
                slow += 1
                nums[slow] = nums[fast]
            fast += 1
            count += 1
            if fast < len(nums) and nums[fast] != nums[fast - 1]:
                count = 0
        return slow + 1

这份写法能够完成题目要求，但处理过程稍微有些绕。

尤其要注意，count 统计的是当前数字被扫描的次数，而不是实际写入数组的次数。即使某个重复元素被跳过，count 仍然会增加。

此外，还需要在进入下一个不同数字之前重置计数。

有没有办法不额外维护 count，直接利用有序数组本身的特点来判断呢？

1.2 利用有效区间判断重复次数

换一种快慢指针的定义。

这次让 slow 指向下一个有效元素应该写入的位置，因此已经保留的有效区间是 [0, slow)。

由于数组有序，相同的元素一定相邻。

如果当前元素 nums[fast] 与 nums[slow - 2] 相同，就说明已经保留的有效区间末尾存在两个相同值，此时不能再写入当前元素。

反过来，如果两者不同，说明当前元素还没有超过允许的重复次数，可以将它写入 nums[slow]，然后让 slow 加一。

不过，访问 slow - 2 之前，需要保证有效区间至少已经保留两个元素。

因此，前两个元素可以直接保留，后面再根据 nums[slow - 2] 判断。

Python 代码：

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow = 0
        fast = 0
        while fast < len(nums):
            if fast < 2 or nums[fast] != nums[slow - 2]:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

例如，输入：

nums = [1, 1, 1, 2, 2, 3]

前两个 1 会直接保留。

当 fast 遍历到第三个 1 时，slow = 2，此时：

nums[fast] = 1
nums[slow - 2] = nums[0] = 1

两者相同，说明已经保留了两个 1，所以跳过当前元素。

继续遍历到 2 时，因为它与 nums[slow - 2] 不同，就可以将其写入有效区间。

最后保留的结果为：

[1, 1, 2, 2, 3]

此时 slow = 5，正好表示有效元素的数量，因此直接返回 slow。

相比第一种写法，这种方法不需要额外记录重复次数，而是通过比较当前元素与有效区间倒数第二个元素，判断是否还能继续保留。

2. LeetCode 88. 合并两个有序数组

这道题给出了两个已经按非递减顺序排列的数组 nums1 和 nums2，要求将它们合并成一个有序数组，并将结果直接保存到 nums1 中。

如果允许创建新数组，思路其实比较简单。

可以使用两个指针 p1 和 p2，分别遍历两个数组。每次比较当前元素，将较小的一个加入结果，再移动对应的指针。

当其中一个数组遍历结束后，把另一个数组中剩余的元素依次加入即可。

这种思路也可以用于合并两个有序链表。

不过，本题要求直接修改 nums1，不能简单地将结果写入一个新数组。

2.1 为什么要从后往前合并？

题目已经为 nums1 预留了足够的空间，长度为 m + n，其中前 m 个元素才是原本的有效数据。

如果直接从前往后写入，可能会覆盖 nums1 中尚未读取的元素。

既然数组末尾已经预留了位置，不妨将思路反过来：每次比较两个数组末尾的元素，把较大的那个放到 nums1 的最后一个可写位置。

这样就不用担心覆盖前面还没有处理的数据。

2.2 三个指针分别负责什么？

这里使用三个指针：

• p1 = m - 1：指向 nums1 原有有效元素的末尾。
• p2 = n - 1：指向 nums2 的末尾。
• tail = m + n - 1：指向 nums1 当前最后一个可写位置。

每次比较 nums1[p1] 和 nums2[p2]。

如果 nums1[p1] 更大，就将它写入 nums1[tail]，然后让 p1 左移。

否则，将 nums2[p2] 写入 nums1[tail]，再让 p2 左移。

无论选择哪个元素，写入完成后，都需要将 tail 左移一格。

例如：

nums1 = [1, 2, 3, 0, 0, 0]，m = 3
nums2 = [2, 5, 6]，n = 3

开始时比较两个数组末尾的 3 和 6。

由于 6 更大，就先将它放到 nums1 的最后一个位置。

接着比较 3 和 5，将 5 放到倒数第二个位置。

不断重复这个过程，最终得到：

[1, 2, 2, 3, 5, 6]

2.3 Python 代码

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        tail = m + n - 1
        p1 = m - 1
        p2 = n - 1
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] > nums2[p2]:
                nums1[tail] = nums1[p1]
                p1 -= 1
            else:
                nums1[tail] = nums2[p2]
                p2 -= 1
            tail -= 1
        while p2 >= 0:
            nums1[tail] = nums2[p2]
            p2 -= 1
            tail -= 1

这里有一个值得注意的细节：为什么第一个 while 结束后，只需要检查 nums2 是否还有剩余元素？

因为我们是从后往前写入的。

如果 nums2 已经处理完，而 nums1 还剩下部分元素，那么这些元素本来就在 nums1 的前面，而且顺序正确，不需要再移动。

反过来，如果 nums1 的有效元素先处理完，就必须将 nums2 剩余的元素继续复制到 nums1 前面。

因此，代码最后只需要补充处理 p2 >= 0 的情况即可。

整个过程不需要额外创建结果数组，时间复杂度为 $O(m+n)$，额外空间复杂度为 $O(1)$。

3. LeetCode 977. 有序数组的平方

这道题给出一个已经按非递减顺序排列的整数数组，要求将每个元素平方后，返回一个同样按非递减顺序排列的新数组。

最直接的方法就是先将所有元素平方，再对结果排序。

这样实现起来很简单，时间复杂度为 $O(n\log n)$。

不过，题目已经告诉我们原数组是有序的，能不能利用这个条件，把时间复杂度优化到 $O(n)$ 呢？

3.1 利用有序数组的特点

这里需要注意，原数组可能包含负数。

例如：

nums = [-4, -1, 0, 3, 10]

平方后得到：

[16, 1, 0, 9, 100]

可以发现，平方后的结果不一定保持原来的顺序。

但仔细观察，有一个特点：

对于有序数组，绝对值最大的元素一定出现在数组的两端。

因此，我们可以使用左右指针，分别指向数组的第一个和最后一个元素。

每次比较两端元素的绝对值，将绝对值较大的元素平方后，放入结果数组的末尾。

这样就可以不断从剩余元素中选出最大的平方值。

这里的处理方向和上一题有些相似：都是从结果数组的末尾开始填充。

3.2 左右指针如何移动？

首先创建一个与原数组等长的结果数组 res，并让 idx 指向最后一个位置。

接着：

1. 比较 abs(nums[left]) 和 abs(nums[right])。
2. 将绝对值较大的元素平方，写入 res[idx]。
3. 移动被选中元素对应的指针。
4. 将 idx 减一，继续填充下一个位置。

由于每次都将当前最大的平方值放到结果数组后面，最终得到的数组自然就是升序排列的。

Python 代码：

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        left = 0
        right = len(nums) - 1
        res = [0] * (right + 1)
        idx = right
        while left <= right:
            if abs(nums[left]) > abs(nums[right]):
                res[idx] = nums[left] * nums[left]
                left += 1
                idx -= 1
            else:
                res[idx] = nums[right] * nums[right]
                right -= 1
                idx -= 1
        return res

这里有一个容易忽略的边界问题：

while left <= right:

为什么使用 <=，而不是 <？

因为当左右指针移动到同一个位置时，这个元素还没有被处理。

如果循环条件写成 left < right，就会直接跳过最后一个元素，导致结果不完整。

所以，必须等到 left > right，才能结束循环。

由于每次都会处理一个元素，左右指针最多移动 n 次，因此时间复杂度为 $O(n)$。

另外，这道题需要创建一个长度为 n 的结果数组，因此额外空间复杂度为 $O(n)$。

4. 总结

这三道题都使用了双指针，但实际处理方式有所区别。

通过这几道题，可以进一步体会到，双指针并不只是让两个变量分别向前或向后移动。

更重要的是先明确：指针代表什么位置、哪些数据已经处理完成，以及移动过程中需要保持什么条件。

例如，第 80 题需要明确有效区间的范围；第 88 题需要考虑原地写入时是否会覆盖数据；第 977 题则要利用原数组的有序性，决定从哪个方向构造答案。

这些问题想清楚之后，指针应该怎样移动，往往也就比较容易确定了。