题目描述
思路解析动画文字版
记住这句「slow 守去重区末尾、fast 找下一个新值搬过来」,下面每一帧都在套它。
快指针 fast 走到下标 1,值 0 和去重区末尾 nums[0]=0 相同——重复值,slow 不动,直接跳过。
快指针 fast 走到下标 2,值 1 和去重区末尾 nums[0]=0 不同——这是个新值,准备搬进去重区。
慢指针 slow 前移到下标 1,把新值 1 搬到 nums[1]。去重区现在是 [0,1]。
快指针 fast 走到下标 3,值 1 和去重区末尾 nums[1]=1 相同——重复值,slow 不动,直接跳过。
快指针 fast 走到下标 4,值 1 和去重区末尾 nums[1]=1 相同——重复值,slow 不动,直接跳过。
快指针 fast 走到下标 5,值 2 和去重区末尾 nums[1]=1 不同——这是个新值,准备搬进去重区。
慢指针 slow 前移到下标 2,把新值 2 搬到 nums[2]。去重区现在是 [0,1,2]。
快指针 fast 走到下标 6,值 2 和去重区末尾 nums[2]=2 相同——重复值,slow 不动,直接跳过。
快指针 fast 走到下标 7,值 3 和去重区末尾 nums[2]=2 不同——这是个新值,准备搬进去重区。
慢指针 slow 前移到下标 3,把新值 3 搬到 nums[3]。去重区现在是 [0,1,2,3]。
快指针 fast 走到下标 8,值 3 和去重区末尾 nums[3]=3 相同——重复值,slow 不动,直接跳过。
快指针 fast 走到下标 9,值 4 和去重区末尾 nums[3]=3 不同——这是个新值,准备搬进去重区。
慢指针 slow 前移到下标 4,把新值 4 搬到 nums[4]。去重区现在是 [0,1,2,3,4]。
快指针 fast 走到下标 10,值 4 和去重区末尾 nums[4]=4 相同——重复值,slow 不动,直接跳过。
快指针 fast 走到下标 11,值 5 和去重区末尾 nums[4]=4 不同——这是个新值,准备搬进去重区。
慢指针 slow 前移到下标 5,把新值 5 搬到 nums[5]。去重区现在是 [0,1,2,3,4,5]。
快指针 fast 走到下标 12,值 6 和去重区末尾 nums[5]=5 不同——这是个新值,准备搬进去重区。
慢指针 slow 前移到下标 6,把新值 6 搬到 nums[6]。去重区现在是 [0,1,2,3,4,5,6]。
快指针 fast 走到下标 13,值 6 和去重区末尾 nums[6]=6 相同——重复值,slow 不动,直接跳过。
快指针扫完整个数组,慢指针停在下标 6。前 7 个 [0,1,2,3,4,5,6] 就是去重结果,返回长度 7(下标 7 之后的旧值不用管)。
边界先想清:空数组返回 0;全相同时去重区只剩第一个。
两个高频追问:指针含义,以及「有序」这个前提一旦去掉就失效。
参考代码
def removeDuplicates(nums): if not nums: return 0 slow = 0 # 去重区末尾 for fast in range(1, len(nums)): if nums[fast] != nums[slow]: # 遇到新值 slow += 1 nums[slow] = nums[fast] # 搬过来 return slow + 1 # 去重后长度复杂度
- 时间:O(n),fast 把数组扫一遍,每个元素只看一次
- 空间:O(1),原地在 nums 上覆盖去重,不开新数组
易错点
面试追问把动画讲成自己的话
追问slow 和 fast 各代表什么?
追问如果数组无序,这个方法还成立吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题