> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/multiple-pointers/shuang-zhi-zhen-zhi-xian-hou-zhi-zhen/remove-duplicates-from-sorted-array-ii.md).

# 80. Remove Duplicates from Sorted Array II

https\://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/description/

Given a sorted array *nums*, remove the duplicates [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm) such that duplicates appeared at most *twice* and return the new length.

Do not allocate extra space for another array, you must do this by **modifying the input array** [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm) with O(1) extra memory.

**Example 1:**

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

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.

It doesn't matter what you leave beyond the returned length.
```

**Example 2:**

```
Given nums = [0,0,1,1,1,1,2,3,3],

Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.

It doesn't matter what values are set beyond the returned length.
```

**Clarification:**

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by **reference**, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

```
// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
```

## Thoughts

对给定数组压缩：重复元素至多出现两次。前后双指针，后指针每次前进一格并比较当前字符和后面是否一致（或到了最后一个字符），一致时跳过；否则在前指针位置开始替换，如果num\[i] 和num\[i-1]也一样说明出现了至少两次，则替换两次。

## Code

```python
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        j = 0
        for i, num in enumerate(nums):
            if i == len(nums) - 1 or num != nums[i + 1]:
                if i > 0 and num == nums[i - 1]:
                    nums[j] = nums[i]
                    j += 1
                nums[j] = nums[i]
                j += 1
        return j
```

```cpp
/*
 * @lc app=leetcode id=80 lang=cpp
 *
 * [80] Remove Duplicates from Sorted Array II
 */
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() <= 2) return nums.size();
        int pos = 2;
        for (int i = pos; i < nums.size(); ++i) {
            if (nums[pos - 1] == nums[pos - 2] && nums[pos - 1] == nums[i]) continue;
            nums[pos++] = nums[i];
        }
        return pos;
    }
};


```

## Analysis

Errors:

1. 先没想到问题本质, 没有数数目, 只想能直接替换, 绕在了nums\[i], nums\[i -2]和pos在i -2和i之间时的关系上了.
2. 没有想到可以让pos和i同时往前走, 这样更清晰. 因为如\[1,1]时如果不是同时走的而是只在else里更新nums\[pos]则会少个1.
3. pos和要返回总数目的关系

时间复杂度O(n). 空间O(1).