力扣网编程第80题：删除有序数组中的重复项（简单）

一. 简介

本文记录一下力扣网上涉及数组的问题：删除有序数组中的重复项。主要练习使用双指针方法来实现。

二. 力扣网编程第80题：删除有序数组中的重复项（简单）

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1：
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。

示例 2：
输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。

题目分析：

题目要求 "原地" 删除数组中重复元素，后面要求写的也很清楚了，不能额外申请内存，在原来数组的基础上完成。那么这里就可以考虑使用双指针完成。

1. 数组已经排序，重复元素会连续出现；

2. 需要保留每个元素最多两次，因此需要检查当前元素是否已经出现两次；

3.如果当前元素已经出现两次，则跳过；否则，保存该元素；

思路分析：使用双指针实现：

慢指针slow: 指向当前可以写入的新元素的位置，即下一个可以放置有效元素的位置。

快指针 fast：遍历数组，保留每个元素是否保留；

解题思路：

1. 特殊情况处理：数组元素<= 2的，直接返回即可；

2. slow指针赋值2， fast指针也赋值 2，也就是说指针都从第三个元素开始；

3. 遍历数组，判断 nums[fast] 是否等于 nums[slow-2]（上上一个元素）：

        nums[fast] != nums[slow-2]，则保存，slow指针后移， fast指针也后移；

       nums[fast] == nums[slow-2]，不保存元素，只是 fast指针后移；

4. 循环结束， slow大小即为新数组的长度（因为slow始终指向下一个可以放置新元素的位置，循环结束后，slow肯定比索引大1）；

C语言实现如下：

int removeDuplicates(int* nums, int numsSize) {//处理特殊情况//元素个数小于2的数组，直接返回即可if(numsSize <= 2) {return numsSize;}//慢指针从第3个元素开始int slow = 2;int fast = 2;while(fast < numsSize) {//判断nums[fast] 是否等于前前一个元素if(nums[fast] != nums[slow-2]) {nums[slow] = nums[fast];slow++;}fast++;}return slow;
}

python实现如下：

class Solution:def removeDuplicates(self, nums: List[int]) -> int:#特殊情况的处理if(len(nums) <= 2):return len(nums)#慢指针，快指针都从第三个元素开始slow = 2fast = 2while(fast < len(nums)):#判断当前元素是否等于前前一个元素if(nums[fast] != nums[slow-2]):nums[slow] = nums[fast]slow += 1fast += 1return slow

可以看出，双指针实现方法满足题目要求。没有申请额外空间（即空间复杂度为O(1)）。