LeetCode 80中等数组
删除有序数组中的重复项 II 图解题解
这道题到底在问什么
给你一个按非递减顺序排列的整数数组 nums，请你原地删除重复出现的元素，使得每个元素最多出现两次，返回删除后数组的新长度。元素的相对顺序应该保持一致。由于在某些语言中不能改变数组长度，你必须将结果放在 nums 的前面部分；超过新长度后面的元素不重要。
- 输入
- nums = [1,1,1,2,2,3]
- 输出
- 5, nums = [1,1,2,2,3,_]
- 输入
- nums = [0,0,1,1,1,1,2,3,3]
- 输出
- 7, nums = [0,0,1,1,2,3,3,_,_]
最优解：一步一步想明白
- 3因为相同数字都挨在一起，只要看结果数组里倒数第二个数，就能知道当前 x 是否会成为第三份重复。
- 4如果 x == nums[slow-2]，说明结果末尾已经有两个 x，再写就会变成第三个，必须跳过。
- 5slow = 0slow 左边是已经整理好的结果区，slow 自己指向下一次写入位置。
- 6if slow < 2: nums[slow] = x; slow += 1前两个元素不可能违反“最多两次”，第一个 1 直接保留。
- 7if slow < 2: nums[slow] = x; slow += 1第二个 1 也允许保留。现在结果区是 [1,1]。
- 8slow >= 2，检查 x != nums[slow - 2]slow=2 时，slow-2=0。结果区倒数第二个数已经是 1，如果再写当前 1，就会出现三个 1。
- 9条件不满足，跳过 x跳过只是不写入当前 x，扫描继续往后走。结果区仍然是 [1,1]。
- 10x != nums[slow - 2] -> nums[slow] = x; slow += 1当前 x=2，结果区倒数第二个是 1，不会形成第三个 2，所以写到 nums[2]。
- 11x != nums[slow - 2] -> nums[slow] = x; slow += 1写第二个 2 前，nums[slow-2]=nums[1]=1，不等于 2，所以第二个 2 合法。
- 12x != nums[slow - 2] -> nums[slow] = x; slow += 13 第一次出现，当然可以保留。结果区变成 [1,1,2,2,3]。
- 13return slow返回长度 5。下标 5 之后的内容不重要，LeetCode 只检查前 5 个位置。
- 16本题 k=2，所以检查 nums[slow-2]。
⚠️ 容易写错的地方
✗ 错：和 nums[slow-1] 比
✓ 对：和 nums[slow-2] 比
最多允许两个相同元素，第三个才要跳过。
✗ 错：删除元素并移动数组
✓ 对：用 slow 原地覆盖
题目只要求前 k 个位置正确，后面不重要。
✗ 错：忘记 slow<2 的保护
✓ 对：前两个元素直接允许写入
否则 slow-2 会越界，也会误判前两个数。
✗ 错：返回整个数组
✓ 对：返回新长度 slow
LeetCode 根据返回长度检查 nums 前缀。
完整代码（Python）
Python
class Solution:
def removeDuplicates(self, nums):
slow = 0
for x in nums:
if slow < 2 or x != nums[slow - 2]:
nums[slow] = x
slow += 1
return slow复杂度
时间复杂度
O(n)
每个元素扫描一次。
空间复杂度
O(1)
原地覆盖，只使用 slow 和当前 x。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 删除有序数组中的重复项 II 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「数组」，换最直接的暴力解会差在哪？+
数组抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。