题目描述
思路解析动画文字版
记住这句「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;全相同时去重区只剩第一个。
两个高频追问:指针含义,以及「有序」这个前提一旦去掉就失效。
参考代码
class Solution: def removeDuplicates(self, 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 上覆盖去重,不开新数组