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

如果写过 26. 删除有序数组中的重复项，可以先回顾它的有效区间：slow 指向已保留部分的末尾，fast 在前面寻找新值。值不同时，将 slow 加一并写入新值；值相同时跳过。最终 [0, slow] 是答案区间，每个值只保留一次。

本题允许每个值最多出现两次。可以增加 count 记录当前值已经扫描了多少次：遇到新值时保留，遇到相同值时再检查次数，超过允许数量就跳过。代码如下：

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

这份写法先比较 fast 和 slow 指向的值：不同则保留，相同则在 count < 2 时保留。相同值分支还需要 slow < fast，避免两个指针重合时重复把当前位置计入有效区间。每轮扫描后，fast 后移、count 加一；如果下一个元素是新值，就把 count 清零。注意 count 统计的是扫描次数，不是实际写入次数，即使跳过重复值也会增加。

我觉得上面的计数写法有些绕。另一种写法让 slow 表示下一个写入位置，有效区间变成 [0, slow)。由于数组有序，如果当前值与 nums[slow-2] 相同，就说明有效区间末尾已经保留了两个相同值，不应继续写入；否则可以保留。fast 小于 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

88. 合并两个有序数组

如果允许创建新数组，可以让 p1、p2 分别遍历 nums1、nums2，每次取较小的元素写入结果，再补上没有取完的部分。链表的合并也可以用类似思路。

但本题要求直接写回 nums1，它已经预留了 m+n 个位置。从前往后写，可能覆盖还没读取的元素；后面的 n 个位置只是占位，可以从那里开始填。于是把思路反过来：每次取两个数组中较大的末尾元素，从后往前写入。

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

这里有三个指针：tail 指向 nums1 的最后一个可写位置，p1 指向 nums1 原有有效元素的末尾，p2 指向 nums2 的末尾。比较后把较大值放到 tail，再移动对应指针。第一个循环结束后，只需补上 nums2 的剩余元素；nums1 如果还有剩余，它们本来就在正确的位置，无须再搬动。

977. 有序数组的平方

先平方再排序很直观，时间复杂度为 O(n log n)。要做到 O(n)，可以利用原数组有序这一点：即使有负数，剩余元素中绝对值最大的也一定在两端。用左右指针比较两端的绝对值，取较大的平方，从结果数组末尾向前填充。这个方向与上一题的原地合并相似。

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

创建与原数组等长的结果数组，让 idx 指向最后一个位置，左右指针则向中间靠拢。循环条件要用 left <= right，两个指针重合时还需要处理最后一个元素；如果只写 left < right，就会漏掉它。

谢谢你读到这里。 ✧