这道题和上一题 LeetCode 27移除元素是亲兄弟连代码结构都几乎一模一样——都是快慢指针原地修改数组。区别在于LeetCode 27 是等于某个值就删这道题是和前一个一样就删。掌握了这个模板一类题全通了。题目长什么样给你一个非严格递增排列的数组nums请你原地删除重复出现的元素使每个元素只出现一次返回删除后数组的新长度。元素的相对顺序应该保持一致。输入nums [0,0,1,1,1,2,2,3,3,4]输出5, nums [0,1,2,3,4,_,_,_,_,_]说人话就是数组已经排好序了把重复的挤掉只留一个剩下的元素往前挪。返回不重复的元素有几个。有两个关键条件值得注意“非严格递增”意味着相等的元素一定挨在一起不会散落在数组各处。这是能用双指针的前提。“保持相对顺序”说明只能从前往后扫不能用左右指针交换。一把就够快慢指针这道题只有一种最优解法——快慢指针。因为要保持顺序左右指针的交换方案直接出局。思路和 LeetCode 27 完全一致慢指针k标记已去重区域的末尾快指针i扫描数组。遇到和前一个不一样的元素就写入k位置。唯一的区别是判断条件LeetCode 27nums[i] ! val不等于目标值就保留LeetCode 26nums[i] ! nums[i-1]和前一个不一样就保留classSolution:defremoveDuplicates(self,nums:List[int])-int:ifnotnums:return0k1foriinrange(1,len(nums)):ifnums[i]!nums[i-1]:nums[k]nums[i]k1returnk注意k从 1 开始——因为第一个元素nums[0]肯定是唯一的前面没有和它重复的。i也从 1 开始因为我们要拿nums[i]和nums[i-1]比。跑一遍示例 2 看看nums [0, 0, 1, 1, 1, 2, 2, 3, 3, 4] ↑ 已确定唯一 i1: nums[1]0 nums[0]0 → 重复跳过 i2: nums[2]1 ≠ nums[1]0 → 新元素! nums[1]1, k2 i3: nums[3]1 nums[2]1 → 重复跳过 i4: nums[4]1 nums[3]1 → 重复跳过 i5: nums[5]2 ≠ nums[4]1 → 新元素! nums[2]2, k3 i6: nums[6]2 nums[5]2 → 重复跳过 i7: nums[7]3 ≠ nums[6]2 → 新元素! nums[3]3, k4 i8: nums[8]3 nums[7]3 → 重复跳过 i9: nums[9]4 ≠ nums[8]3 → 新元素! nums[4]4, k5 结果: nums [0, 1, 2, 3, 4, _, _, _, _, _], k 5维度值说明时间O(n)每个元素只看一次空间O(1)只用了一个变量k和 LeetCode 27 放在一起看这两道题的代码几乎一样放在一起对比就清楚了LeetCode 27移除元素 LeetCode 26删除重复项 ───────────────────── ───────────────────── k 0 k 1 for i in range(len(nums)): for i in range(1, len(nums)): if nums[i] ! val: if nums[i] ! nums[i-1]: nums[k] nums[i] nums[k] nums[i] k 1 k 1 return k return k三处区别区别LeetCode 27LeetCode 26起始值k 0第一个元素也要判断k 1第一个元素直接保留遍历起点i 0i 1需要和前一个比较判断条件nums[i] ! valnums[i] ! nums[i-1]本质上是同一个模板只是保留条件不同。LeetCode 27 的保留条件是不等于某个值这道题的保留条件是和前一个不一样。这道题教会我什么有序是最大的提示题目说非严格递增这意味着相等的元素一定连续排列。如果数组是无序的nums[i] ! nums[i-1]这个判断就废了——不相邻的重复元素会漏掉。所以看到有序数组第一反应就应该是重复元素一定相邻可以用双指针。快慢指针是一个万能模板k 起始位置 for i in range(遍历范围): if 满足保留条件: nums[k] nums[i] k 1 return k这个模板能解决所有原地过滤数组类的问题只需要改三个地方起始值、遍历范围、保留条件。LeetCode 27、LeetCode 26、LeetCode 283移动零都是这个套路。边界条件不能忘if not nums: return 0这一行很容易漏掉。当数组为空时k 1会导致越界。LeetCode 27 没有这个问题因为空数组的range(len(nums))直接不执行循环k 0自然返回。但 LeetCode 26 的k从 1 开始空数组必须单独处理。完整测试代码fromtypingimportListclassSolution:defremoveDuplicates(self,nums:List[int])-int:ifnotnums:return0k1foriinrange(1,len(nums)):ifnums[i]!nums[i-1]:nums[k]nums[i]k1returnkif__name____main__:sSolution()nums[1,1,2]ks.removeDuplicates(nums)print(fk{k}, nums{nums[:k]})nums[0,0,1,1,1,2,2,3,3,4]ks.removeDuplicates(nums)print(fk{k}, nums{nums[:k]})nums[1]ks.removeDuplicates(nums)print(fk{k}, nums{nums[:k]})nums[1,1,1,1]ks.removeDuplicates(nums)print(fk{k}, nums{nums[:k]})nums[1,2,3,4]ks.removeDuplicates(nums)print(fk{k}, nums{nums[:k]})相关题目推荐LeetCode 27 · 移除元素同一个模板保留条件不同LeetCode 80 · 删除有序数组中的重复项 II进阶版允许最多出现两次LeetCode 283 · 移动零同一个模板把零移到末尾