LeetCode 27 · 移除元素：双指针的两种打开方式

这道题和 LeetCode 26删除有序数组中的重复项是一对姐妹题核心都是原地修改数组。有意思的是这道题的双指针有两种完全不同的玩法——一个从前往后一个两头往中间。两种思路都值得掌握因为它们代表了双指针最经典的两种模式。题目长什么样给你一个数组nums和一个值val你需要原地移除所有数值等于val的元素。元素的顺序可能发生改变。然后返回nums中与val不同的元素的数量。输入nums [0,1,2,2,3,0,4,2], val 2输出5, nums [0,1,4,0,3,_,_,_]说人话就是把数组里所有等于val的元素删掉把剩下的元素挤到数组前面返回剩下几个。后面留了啥无所谓评测机不看。第一反应快慢指针一个读一个写最直观的想法——用一个指针i扫描整个数组另一个指针k记录有效区域的末尾。遇到不是val的元素就写入k的位置然后k往前推一步。classSolution:defremoveElement(self,nums:List[int],val:int)-int:k0foriinrange(len(nums)):ifnums[i]!val:nums[k]nums[i]k1returnk跑一遍示例 2 看看过程nums [0, 1, 2, 2, 3, 0, 4, 2], val 2 i0 k0 i0: nums[0]0 ≠ 2 → nums[0]0, k1 i1: nums[1]1 ≠ 2 → nums[1]1, k2 i2: nums[2]2 2 → 跳过 i3: nums[3]2 2 → 跳过 i4: nums[4]3 ≠ 2 → nums[2]3, k3 i5: nums[5]0 ≠ 2 → nums[3]0, k4 i6: nums[6]4 ≠ 2 → nums[4]4, k5 i7: nums[7]2 2 → 跳过 结果: nums [0,1,3,0,4,_,_,_], k 5维度值说明时间O(n)每个元素只看一次空间O(1)只用了两个变量这就是最标准的解法。代码简洁思路清晰面试写这个完全够用。但仔细想想——当要删除的元素很少时比如数组有 1000 个元素只有最后 1 个等于val这个方法还是会把前面 999 个元素都复制一遍虽然是复制到自己的位置。能不能更聪明一点换个思路左右指针遇到了就换掉如果题目说顺序可以变——那事情就好办了。等于val的元素我们根本不需要保留直接从数组末尾拿一个元素来覆盖它就行。classSolution:defremoveElement(self,nums:List[int],val:int)-int:left,right0,len(nums)-1whileleftright:ifnums[left]val:nums[left]nums[right]right-1else:left1returnleft跑一遍示例 1 看看nums [3, 2, 2, 3], val 3 ↑left ↑right Step 1: nums[0]3 3 → 用 nums[3]3 覆盖 → [3,2,2,3], right2 Step 2: nums[0]3 3 → 用 nums[2]2 覆盖 → [2,2,2,3], right1 Step 3: nums[0]2 ≠ 3 → left1 Step 4: nums[1]2 ≠ 3 → left2 Step 5: left2 right1 → 结束 结果: k2, nums前2个 [2,2]再跑一遍示例 2nums [0,1,2,2,3,0,4,2], val 2 ↑left ↑right Step 1: nums[0]0 ≠ 2 → left1 Step 2: nums[1]1 ≠ 2 → left2 Step 3: nums[2]2 2 → 用 nums[7]2 覆盖 → [0,1,2,2,3,0,4,2], right6 Step 4: nums[2]2 2 → 用 nums[6]4 覆盖 → [0,1,4,2,3,0,4,2], right5 Step 5: nums[2]4 ≠ 2 → left3 Step 6: nums[3]2 2 → 用 nums[5]0 覆盖 → [0,1,4,0,3,0,4,2], right4 Step 7: nums[3]0 ≠ 2 → left4 Step 8: nums[4]3 ≠ 2 → left5 Step 9: left5 right4 → 结束 结果: k5, nums前5个 [0,1,4,0,3]维度值说明时间O(n)每个元素最多访问一次空间O(1)只用了两个变量赋值次数最多 n 次比快慢指针最多 2n 次更少两种解法放在一起看解法时间空间赋值次数保持顺序快慢指针O(n)O(1)最多 2n✅ 保持左右双指针O(n)O(1)最多 n❌ 不保证快慢指针万能解法适用于所有原地移除/过滤类问题而且保持元素原始顺序。左右双指针当val很少时优势明显赋值次数更少但会打乱顺序。面试时先写快慢指针然后主动提如果顺序不重要还可以用左右指针减少赋值次数——这种递进思考就是面试官想看到的。这道题教会我什么同一个技巧不同的打开方式双指针不是一种固定写法而是一种思想——用两个标记位置来解决问题。快慢指针是一个读一个写左右指针是两头往中间收敛。两种模式在很多题目里都能见到快慢指针删除重复元素、移动零、滑动窗口左右指针两数之和有序数组、盛水容器、回文判断顺序可以变不是废话题目特意说元素的顺序可能发生改变这个条件不是白给的——它直接打开了左右指针的解法。和 LeetCode 88 一样题目里的每一个条件都值得多想一步。O(n) 也能继续优化两种解法时间复杂度都是 O(n)但实际赋值次数差了一倍。面试中如果能说出虽然都是 O(n)但赋值操作次数不同说明你对复杂度的理解已经不局限于大 O 符号了。完整测试代码fromtypingimportListclassSolution:defremoveElement(self,nums:List[int],val:int)-int:k0foriinrange(len(nums)):ifnums[i]!val:nums[k]nums[i]k1returnkclassSolution2:defremoveElement(self,nums:List[int],val:int)-int:left,right0,len(nums)-1whileleftright:ifnums[left]val:nums[left]nums[right]right-1else:left1returnleftif__name____main__:s1Solution()s2Solution2()nums[3,2,2,3]ks1.removeElement(nums,3)print(f解法一: k{k}, nums{nums[:k]})nums[0,1,2,2,3,0,4,2]ks1.removeElement(nums,2)print(f解法一: k{k}, nums{nums[:k]})nums[3,2,2,3]ks2.removeElement(nums,3)print(f解法二: k{k}, nums{nums[:k]})nums[0,1,2,2,3,0,4,2]ks2.removeElement(nums,2)print(f解法二: k{k}, nums{nums[:k]})nums[]ks1.removeElement(nums,0)print(f解法一: k{k}, nums{nums[:k]})nums[1]ks1.removeElement(nums,1)print(f解法一: k{k}, nums{nums[:k]})相关题目推荐LeetCode 26 · 删除有序数组中的重复项快慢指针的经典应用顺序敏感LeetCode 283 · 移动零快慢指针的变体把零移到末尾LeetCode 80 · 删除有序数组中的重复项 IILeetCode 26 的进阶版允许重复两次