LeetCode 80. 删除有序数组中的重复项 II
题目描述
题意分析
给定非递减排列的整数数组，原地删除多余重复项，使每个值最多保留两次，并保持剩余元素的相对顺序。
返回保留下来的元素个数
k，并把这些元素放到数组前k个位置。只返回数量还不够，前缀内容也必须正确；k之后的元素无需清零或删除，且不能借助另一个数组保存结果。
解法：慢指针保留最多两个重复项
核心思路
[!blue]
从左到右读取元素，用
write表示已经保留的数量，也就是下一次写入的位置。在处理当前元素前，nums[0..write-1]始终是已读部分整理好的有序结果，每个值至多出现两次。当前缀不足两个元素时，直接保留不会超过次数限制。否则，将当前值
num与结果前缀的倒数第二项nums[write - 2]比较。若两者相等，前缀有序且后续读取值不会变小，倒数最后一项也必然等于
num。说明这个值已经保留两次，再写就是第三次，必须跳过。若两者不相等，前缀就不可能已经有两份当前值，因此可以追加。这一判断利用有序性，无需单独维护每个数字的计数。接受时写入
nums[write]并右移write，拒绝时只继续读取。写入次数不可能超过读取次数，所以写指针始终不在读指针前面，覆盖的都是当前或已读位置，不会破坏尚未读取的元素。全部处理后，这个有效前缀就是答案。
解题步骤
- 将有效长度
write初始化为零。- 依次读取数组中的每个
num。- 若
write < 2，直接保留；否则只有num != nums[write - 2]时才保留。- 保留时写入
nums[write]，然后将write加一；跳过时不改变它。- 遍历结束返回
write，数组尾部不再处理。
代码实现
class Solution {
public int removeDuplicates(int[] nums) {
int write = 0;
for (int num : nums) {
// 与有效前缀倒数第二项比较，保证同值最多保留两次。
if (write < 2 || num != nums[write - 2]) {
nums[write++] = num;
}
}
return write;
}
}
func removeDuplicates(nums []int) int {
write := 0
for _, num := range nums {
// 与有效前缀倒数第二项比较，保证同值最多保留两次。
if write < 2 || num != nums[write-2] {
nums[write] = num
write++
}
}
return write
}
复杂度分析
- 时间复杂度：$O(n)$，每个元素读取一次，至多写入一次。
- 空间复杂度：$O(1)$，结果覆盖到原数组前缀，只维护固定数量的变量。
关键点总结
[!green]
- 原地删除转化为按条件覆盖写入，结果长度和下一写入位置由同一个指针表示。
- 有序性让相同值连在一起，比较结果倒数第二项即可知道当前值是否已有两份。
- 判断依据是已整理前缀；读取位置附近的旧元素不代表实际保留数量。
- 写指针不超过读指针，保证一边遍历一边覆盖不会破坏后续输入。
易错点总结
[!yellow]
- 比较
nums[write - 1]会限制为每个值只保留一次，不符合本题。- 必须先判断
write < 2，利用短路求值避免访问负下标。- 不能改为比较读取下标前两项，跳过和覆盖后它们不再代表结果中的保留次数。
- 返回
write - 1会把最后有效下标误当成长度；正确长度就是write。- 只统计保留数量而不覆盖写入，无法满足题目对数组前缀内容的要求。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 26. 删除有序数组中的重复项 | 简单 | 同样用写指针压缩有序重复段，原题每个值只保留一次，本题保留至多两次。 |
| 27. 移除元素 | 简单 | 同样原地筛选保留元素，但本题保留条件由重复次数决定而非固定目标值。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！