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

题目

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

解题思路

我的思路大致如下，使用三个独立索引（指针）i,j,k，索引i用于指向结果数组末元素的后一位元素，索引j用于指向每个重复段的第一个元素，索引k用于指向每个重复段的后一个元素。所以k-j便是每个重复段中相同元素的个数，通过判断重复次数，移动索引i进行移动赋值（如果次数为1，则赋值一次；次数大于等于2，则赋值两次）。每次移动赋值完成后，j = k将k的值赋给j，使j指向下一段的第一个元素。依次类推，直到遍历到倒数第二个重复段。对于最后一个重复段，因为无法找到下一个重复段的首元索引k，所以无法得到最后一个重复段的长度，进而无法判断。所以需要单独计算一下最后一个重复段的长度，单独进行索引i的移动赋值。我的菜鸟解法如下（想了好久www）：

class Solution:def removeDuplicates(self, nums: List[int]) -> int:n = len(nums)if n == 0 or n ==1:return n# nums[0,i]为非重复数列i = 0j = 0k = j + 1while k <= n-1:if nums[j] != nums[k]:if k - j == 1:nums[i] = nums[j]i += 1elif k - j >= 2:nums[i] = nums[j]nums[i+1] = nums[j]i += 2j = kk += 1nums[i] = nums[j] if n-1-j >= 1:nums[i+1] = nums[j]return i+2return i+1

解题思路【学习】

双指针

原文链接：【负雪明烛】动画题解，帮助理清思路 - 删除有序数组中的重复项 II - 力扣（LeetCode）

class Solution(object):def removeDuplicates(self, nums):slow = 0for fast in range(len(nums)):if slow < 2 or nums[fast] != nums[slow - 2]:nums[slow] = nums[fast]slow += 1return slow作者：fuxuemingzhu
链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/solution/fu-xue-ming-zhu-dong-hua-ti-jie-bang-zhu-yrx5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

看了大佬的题解真是弗如远甚，我只能妙妙妙！特别是nums[fast] != nums[slow - 2]这一段，等式不成立，则说明nums[fast]所指向的元素未重复两次；等式成立，则说明nums[fast]所指向的元素已经重复两次了，巧妙地代替了计数的功能。