LeetCode 80. 删除有序数组中的重复项 II
目录
题目描述
题意分析
给定一个非递减排列的整数数组，要求原地改写它，使得每个不同的值最多保留两份，并返回改写后有效部分的长度。判题只看返回长度
k以及数组前k个位置的内容，后面剩下什么都不重要。约束里有两个信号。数组已经有序，意味着值相同的元素必然连成一段，判断「这个值已经保留了几个」不需要任何计数结构，只看邻近的几个位置就够。题目要求原地完成、额外空间 $O(1)$，等于直接排除了「新开一个数组再拷回去」的写法。
边界主要有三处：数组长度小于等于 2 时任何元素都不用删；某个值恰好出现两次时要全保留而不是删一个；某个值出现很多次时要连续跳过一长串。返回值是长度而不是下标，差一就会整体错位。
解法：慢指针保留最多两个重复项
核心思路
题目只要求数组前
k个位置正确，因此不必真的删除并搬移元素，只需用读写双指针原地重写有效前缀。
write既表示有效前缀长度，也表示下一个写入位置。遍历当前元素num时，write < 2表示前两个元素一定可以保留；否则，仅当num != nums[write - 2]时写入。循环不变量是：
nums[0..write-1]始终是已读元素的合法结果，有序且每个值最多出现两次。为什么只比较倒数第二个元素？结果前缀仍然有序。若
num == nums[write - 2]，那么nums[write - 2]、nums[write - 1]和num必然相等，当前元素是第三份；若不相等，前缀中最多只有一份num，可以安全追加。写入次数不会超过读取次数，所以覆盖的都是已经读取过的位置。
解题步骤
- 初始化
write = 0。- 从左到右读取每个
num。- 若
write < 2或num != nums[write - 2]，将num写到nums[write]，再令write++。- 否则跳过当前元素。
- 遍历结束后返回
write，无需处理数组尾部。对
[1,1,1,2,2,3]，前三个1只写入两个；两个2都与结果前缀倒数第二位不同，均被保留；最终前缀为[1,1,2,2,3]，返回5。
代码实现
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)$，直接改写原数组。
关键点总结
- 原地删除应转化为覆盖写入，数组尾部残留内容不影响答案。
- 判断对象是已经整理好的结果前缀，而不是原数组中的固定偏移位置。
- 比较
nums[write - 2]对应“最多保留两份”；推广到最多保留m份时比较nums[write - m]。write同时表示有效长度和下一写入位置，返回时无需再加减一。
易错点总结
- 比较
nums[write - 1]：会退化成每个值最多保留一份。- 直接访问
nums[write - 2]而不判断write < 2：短数组会出现负下标。- 比较原数组的
nums[i - 2]：发生覆盖或跳过后，它不再代表结果前缀中的保留数量。- 返回
write - 1：write是长度，不是最后一个有效下标。- 清理数组尾部：题目只检查前
write个元素，这一步没有必要。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 26. 删除有序数组中的重复项 | 简单 | 每个值只保留一份的基础版本 |
| 27. 移除元素 | 简单 | 按值过滤，与前缀内容无关 |
| 283. 移动零 | 简单 | 保序前移后还需回填尾部 |
| 443. 压缩字符串 | 中等 | 重写内容与原内容长度不等 |
| 75. 颜色分类 | 中等 | 无序输入下的三向双指针划分 |