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

如果你写过 26. 删除有序数组中的重复项 这个题，那么这个稍微多了点条件和判定，26题是重复元素保留一个就行了，我们无脑让fast在前面探路，只要和slow指针指向的元素不同，就让把fast放到slow+1这个位置上。然后fast遇到和slow相同的值，就会跳过，最后[0,slow]这个区间是答案，每个值只会出现一次。

这个题让重复元素最多出现两个，那么无非就是加上一个count进行一个计数，然后分类讨论，一种是值不同，那肯定就要加到前面，一种是值相同，但是count数量不超过2,那么也要加到前面。代码如下：

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的值是不是相同，不相同那就要添加进去，相同的话再考虑有没有超过2个，不超过2个就添加进去，超过2个就跳过，然后这里还需要判断slow<fast。因为我们的slow指针指向的有效区间，slow这个值是有效的，假如slow和fast重合，就会存在多添加一个元素的情况了。随后让fast指针后移，然后当前这个数我们添加到有效区间了，count就+1,最后判断下一个元素是不是新元素，是的话就让count清零。

不过这种写法其实感觉还是有点绕的。还有另外一种更简洁的写法,这里的slow代表的是即将写入的位置，不在有效区间，然后我们判断slow-2的位置和fast的位置是不是相同，因为值是连续的，如果相同的话，说明slow-1也是这个值，slow-2也是这个值，已经有两个了，那就不符合条件了，如果不相同，那就添加进去。当然，在0和1的时候n-2会越界，但是我fast<2的话，我们也可以无脑把元素放进去，直接放两个元素不管一样不一样，也不是符合题目条件的，肯定也是没问题的。

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指向num1,用指针p2指向num2,然后判断是nums1[p1]小还是nums[p2]小，然后依次放到新数组，最后检查哪个数组的元素没放完，依次追加到新数组就可以了。

但是这个题给我们说了，num1直接就是开辟了m+n的一个空间大小，我们要在num1和num2上面做动作，不能开辟新数组。但是此时从前往后走，又会篡改num1前面的数据，就会丢数据了。此时我们就要逆向思维一下，num1后面的都是0,只是占位的，都是无用数据，我们可以随便覆盖不是吗。上面的思路是从小到大，从前往后放，那这个我们逆向思路就是从大到小，从后往前放就可以了。代码如下。

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

总的来说就是需要3个指针，tail指向num1的末尾，p1指向num1的末尾，p2指向num2的末尾，然后依次判断两个数组的末尾哪个数字大就从后往前放就行了，其中在第一个while循环结束后我们不需要判断num1是否走完，因为num1的数据本来就在前面，如果num1数据没拿完，也是不用管的，只需要考虑如果num2数据没拿完，依次往前面放就可以了。

977. 有序数组的平方

这个题的话，先把所有数字平方，然后再进行排序，很简单，但是时间复杂度比较快也需要O（nlog(n)）。想要时间复杂度为O（n）的话，就需要开辟一个新的数组，虽然数组存在负数，但是也是有序的，我们可以从两端向中间逼近。虽然现在不确定中间哪个最小，但是两侧的肯定有一个数是最大的，和上一个题目有几分类似，一样是从大到小的一个思路，很容易就解决了。

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指向最后一个位置，从后往前进行一个填充，然后while的判断条件的话这里需要是left<right，不然就会漏掉一个元素了。