80. 删除有序数组中的重复项 II
题目描述
输入数组 nums，它已按非递减顺序排好。
在原数组上删去多余的重复元素，使每个值最多保留两个，且保持原有的相对顺序。设剩下 k 个元素，它们要放在 nums 的前 k 个位置，k 之后的位置放什么都可以。
函数返回 k。只能用 O(1) 额外空间，不能另开数组。
本页的输出写成 [k, nums 的前 k 个元素]。
示例 1
输入：nums = [1,1,1,2,2,3] 输出：[5,[1,1,2,2,3]]
解释：三个 1 只保留两个，剩下 5 个元素 [1,1,2,2,3]。
示例 2
输入：nums = [0,0,1,1,1,1,2,3,3] 输出：[7,[0,0,1,1,2,3,3]]
解释：四个 1 只保留两个，剩下 7 个元素。
数据范围
1 <= nums.length <= 3 * 10^4-10^4 <= nums[i] <= 10^4nums已按升序排列。
解题思路
快慢指针。k 是保留前缀的长度，也是下一个写入位置。读到 x 时，如果前缀不足两个，或 nums[k−2] ≠ x，就把 x 写到 nums[k]。数组有序，nums[k−2] == x 说明前缀末尾已经有两个 x，再放就是第三个。
为什么正确
nums[:k] 是已读部分中每个值最多保留两次后的结果，并且仍然有序。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
要和前缀里的 nums[k−2] 比，不是和原数组的 nums[i−2] 比：原位置可能已被覆盖，也可能包含已丢弃的重复值。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
k = 0
for x in nums:
if k < 2 or nums[k - 2] != x:
nums[k] = x
k += 1
return kclass Solution {
public int removeDuplicates(int[] nums) {
int k = 0;
for (int x : nums) {
if (k < 2 || nums[k - 2] != x) {
nums[k] = x;
k++;
}
}
return k;
}
}class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int k = 0;
for (int x : nums) {
if (k < 2 || nums[k - 2] != x) {
nums[k] = x;
k++;
}
}
return k;
}
};func removeDuplicates(nums []int) int {
k := 0
for _, x := range nums {
if k < 2 || nums[k-2] != x {
nums[k] = x
k++
}
}
return k
}var removeDuplicates = function(nums) {
let k = 0;
for (const x of nums) {
if (k < 2 || nums[k - 2] !== x) {
nums[k] = x;
k++;
}
}
return k;
};function removeDuplicates(nums: number[]): number {
let k = 0;
for (const x of nums) {
if (k < 2 || nums[k - 2] !== x) {
nums[k] = x;
k++;
}
}
return k;
}