题目描述
思路解析动画文字版
核心就一句话:当前数和「已写区倒数第二个」相等,才说明已经有两个了、要丢;否则保留。下面每一帧都在套这条判断。
开始前:写指针 k=0,读指针 i=0。绿色 i 是正在看的数,蓝色 k 是接下来要写的位置。
读指针 i 走到下标 0,看到 0。写指针 k=0 还小于 2,前两个位置无条件保留,要把 nums[0]=0 写下来。
保留:把 0 写到第 0 位(蓝色写指针处),写指针 k 前进到 1。绿色高亮的就是已经定稿的结果区。
读指针 i 走到下标 1,看到 0。写指针 k=1 还小于 2,前两个位置无条件保留,要把 nums[1]=0 写下来。
保留:把 0 写到第 1 位(蓝色写指针处),写指针 k 前进到 2。绿色高亮的就是已经定稿的结果区。
读指针 i 走到下标 2,看到 1。当前数 1 和已写区倒数第二个 nums[0]=0 不相等,说明 1 还没攒够两个,保留。
保留:把 1 写到第 2 位(蓝色写指针处),写指针 k 前进到 3。绿色高亮的就是已经定稿的结果区。
读指针 i 走到下标 3,看到 1。当前数 1 和已写区倒数第二个 nums[1]=0 不相等,说明 1 还没攒够两个,保留。
保留:把 1 写到第 3 位(蓝色写指针处),写指针 k 前进到 4。绿色高亮的就是已经定稿的结果区。
读指针 i 走到下标 4,看到 1。当前数 1 和已写区倒数第二个 nums[2]=1 相等,说明 1 已经有两个了,这第三个跳过不写。
跳过:这第三个 1 是多余的(标红),不写进结果区,写指针 k 留在原地不动。
读指针 i 走到下标 5,看到 1。当前数 1 和已写区倒数第二个 nums[2]=1 相等,说明 1 已经有两个了,这第三个跳过不写。
跳过:这第三个 1 是多余的(标红),不写进结果区,写指针 k 留在原地不动。
读指针 i 走到下标 6,看到 2。当前数 2 和已写区倒数第二个 nums[2]=1 不相等,说明 2 还没攒够两个,保留。
保留:把 2 写到第 4 位(蓝色写指针处),写指针 k 前进到 5。绿色高亮的就是已经定稿的结果区。
读指针 i 走到下标 7,看到 3。当前数 3 和已写区倒数第二个 nums[3]=1 不相等,说明 3 还没攒够两个,保留。
保留:把 3 写到第 5 位(蓝色写指针处),写指针 k 前进到 6。绿色高亮的就是已经定稿的结果区。
读指针 i 走到下标 8,看到 3。当前数 3 和已写区倒数第二个 nums[4]=2 不相等,说明 3 还没攒够两个,保留。
保留:把 3 写到第 6 位(蓝色写指针处),写指针 k 前进到 7。绿色高亮的就是已经定稿的结果区。
扫完整趟,写指针停在 7。数组前 7 个(绿色)就是答案 [0,0,1,1,2,3,3],每个数最多两个。
三个高频追问:k 的双重含义、去重 I 的改法、以及为什么原地覆盖是安全的。
参考代码
def removeDuplicates(nums): k = 0 # 写指针:下一个该写的位置 for x in nums: # x 是当前读到的数 if k < 2 or nums[k-2] != x: # 没满两个 → 保留 nums[k] = x k += 1 return k # 新长度复杂度
- 时间:O(n),读指针 i 把数组从头到尾扫一遍,每个数只看一次
- 空间:O(1),只用一个写指针 k,在原数组上覆盖,不开额外数组
易错点
面试追问把动画讲成自己的话
追问写指针 k 代表什么?
追问如果题目改成「每个元素最多保留一次」(去重 I)怎么改?
追问为什么可以直接在原数组上覆盖、不怕把还没读的数冲掉?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
轮转数组
LeetCode 189 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题