LeetCode 80 · 删除有序数组中的重复项 II：通用模板的威力

LeetCode 26 要求每个元素最多出现一次这道题放宽到最多出现两次。看起来只是把1改成了2但这个小改动背后藏着一个通用的快慢指针模板——把2换成任意整数m代码几乎不用动。这就是模板的威力改一个数字通吃一整类题。题目长什么样给你一个有序数组nums请你原地删除重复出现的元素使得出现次数超过两次的元素只出现两次返回删除后数组的新长度。输入nums [0,0,1,1,1,1,2,3,3]输出7, nums [0,0,1,1,2,3,3]说人话就是数组已经排好序了每个元素最多保留两个多余的删掉。和 LeetCode 26 唯一的区别就是最多保留几个——26 题是 1 个这道题是 2 个。从 LeetCode 26 说起改一个数字就行先回顾一下 LeetCode 26 的代码# LeetCode 26最多保留 1 个defremoveDuplicates(self,nums):ifnotnums:return0k1# 前 1 个直接保留foriinrange(1,len(nums)):# 从第 1 个开始扫ifnums[i]!nums[k-1]:# 和倒数第 1 个已保留元素比nums[k]nums[i]k1returnk现在要改成最多保留 2 个只需要做三处修改# LeetCode 80最多保留 2 个defremoveDuplicates(self,nums):iflen(nums)2:returnlen(nums)k2# 前 2 个直接保留foriinrange(2,len(nums)):# 从第 2 个开始扫ifnums[i]!nums[k-2]:# 和倒数第 2 个已保留元素比nums[k]nums[i]k1returnk改动点就三个1→21→2k-1→k-2。逻辑完全一样。为什么nums[k-2]就够了这是这道题最精妙的地方。很多第一反应是我需要计数器记录当前元素出现了几次——不需要。关键推理因为数组是有序的相同元素一定相邻。 nums[k-2] 是已保留区域的倒数第二个位置。 如果 nums[i] ! nums[k-2] 说明 nums[i] 是个新元素或者虽然出现过但不超过两次 可以安全保留。 如果 nums[i] nums[k-2] 说明 nums[i] 至少是第三次出现了因为前面已经有 nums[k-2] 和它之间的那个 必须跳过。画个图更清楚已保留区域: [..., x, x, ...] ← nums[k-2] 和 nums[k-1] 可能都是 x ↑ nums[k-2] 当前扫描到 nums[i] x → x nums[k-2]说明前面已经有两个 x 了这是第三个 → 跳过 当前扫描到 nums[i] y (y ≠ x) → y ≠ nums[k-2]说明 y 出现不超过两次 → 保留不需要计数器不需要额外状态一个比较就够了。跑一遍示例示例 1nums [1,1,1,2,2,3]前两个直接保留: [1, 1, _, _, _, _], k 2 i2: nums[2]1, nums[k-2]nums[0]1 → 11, 第三次出现, 跳过 i3: nums[3]2, nums[k-2]nums[0]1 → 2≠1, 保留! nums[2]2, k3 i4: nums[4]2, nums[k-2]nums[1]1 → 2≠1, 保留! nums[3]2, k4 i5: nums[5]3, nums[k-2]nums[2]2 → 3≠2, 保留! nums[4]3, k5 结果: [1, 1, 2, 2, 3, _], k 5示例 2nums [0,0,1,1,1,1,2,3,3]前两个直接保留: [0, 0, _, _, _, _, _, _, _], k 2 i2: nums[2]1, nums[0]0 → 1≠0, 保留! nums[2]1, k3 i3: nums[3]1, nums[1]0 → 1≠0, 保留! nums[3]1, k4 i4: nums[4]1, nums[2]1 → 11, 第三次出现, 跳过 i5: nums[5]1, nums[2]1 → 11, 第四次出现, 跳过 i6: nums[6]2, nums[2]1 → 2≠1, 保留! nums[4]2, k5 i7: nums[7]3, nums[3]1 → 3≠1, 保留! nums[5]3, k6 i8: nums[8]3, nums[4]2 → 3≠2, 保留! nums[6]3, k7 结果: [0, 0, 1, 1, 2, 3, 3, _, _], k 7通用模板允许保留 m 个把2抽象成参数m就得到了一个通用模板defremoveDuplicates(self,nums:List[int],m:int2)-int:iflen(nums)m:returnlen(nums)kmforiinrange(m,len(nums)):ifnums[i]!nums[k-m]:nums[k]nums[i]k1returnkm的值对应题目m 1LeetCode 26每个元素最多出现 1 次m 2LeetCode 80每个元素最多出现 2 次m 3如果有 LeetCode 80 变体要求最多 3 次m 任意同一套代码改参数即可三道题放在一起看题目保留条件起始 k遍历起点比较LeetCode 27nums[i] ! val00和目标值比LeetCode 26nums[i] ! nums[k-1]11和前 1 个比LeetCode 80nums[i] ! nums[k-2]22和前 2 个比LeetCode 27 是过滤模式和固定值比26 和 80 是去重模式和已保留区域的元素比。去重模式的规律就是允许保留几个就和倒数第几个比。这道题教会我什么抨模板比抻代码更有价值如果你把 LeetCode 26 的代码背下来碰到 LeetCode 80 可能会懵——但如果你理解了和倒数第 m 个比这个模式改一个数字就过了。面试时也是一样面试官不会考你原题但会考你能不能把已知的模式迁移到新场景。不需要计数器第一反应往往是记录当前元素出现了几次但其实有序数组的特性让问题变得简单——只要和nums[k-m]比一下就知道是第几次出现了。这种用位置关系代替显式计数的技巧在数组和链表题里非常常见。边界条件len(nums) 2LeetCode 26 的边界是空数组if not numsLeetCode 80 的边界是长度不足 2if len(nums) 2。通用模板的边界是if len(nums) m。模板越通用边界条件越要小心。完整测试代码fromtypingimportListclassSolution:defremoveDuplicates(self,nums:List[int])-int:iflen(nums)2:returnlen(nums)k2foriinrange(2,len(nums)):ifnums[i]!nums[k-2]:nums[k]nums[i]k1returnkif__name____main__:sSolution()nums[1,1,1,2,2,3]ks.removeDuplicates(nums)print(fk{k}, nums{nums[:k]})nums[0,0,1,1,1,1,2,3,3]ks.removeDuplicates(nums)print(fk{k}, nums{nums[:k]})nums[1,1,1,1,1]ks.removeDuplicates(nums)print(fk{k}, nums{nums[:k]})nums[1,2,3,4,5]ks.removeDuplicates(nums)print(fk{k}, nums{nums[:k]})nums[1,1]ks.removeDuplicates(nums)print(fk{k}, nums{nums[:k]})nums[1]ks.removeDuplicates(nums)print(fk{k}, nums{nums[:k]})相关题目推荐LeetCode 26 · 删除有序数组中的重复项m1的特例LeetCode 27 · 移除元素过滤模式和固定值比较LeetCode 283 · 移动零同一个快慢指针模板