【LeetCode 27. 移除元素】C++ 范围 for 极简实现与原理解析
【LeetCode 27. 移除元素】C++ 范围 for 极简实现与原理解析
本文将详细讲解 LeetCode 第 27 题「移除元素」的高效解法，重点介绍如何使用 C++11 范围 for 循环实现原地修改，并深入分析其原理与性能优势。
一、题目回顾
给你一个数组nums和一个值val，你需要原地移除所有数值等于val的元素。元素的顺序可能发生改变。然后返回nums中与val不同的元素的数量。
- 要求：原地修改数组，使前
k个元素为有效元素，其余元素无需关心。 - 返回值：有效元素的数量
k。
示例：
- 输入：
nums = [3,2,2,3],val = 3 - 输出：
2，数组前两位变为[2,2]
二、核心思路：双指针法
这道题的经典解法是双指针法：
- 用一个慢指针
k记录有效元素的存放位置。 - 遍历数组，遇到不等于
val的元素，就将其写入nums[k]，并将k后移。 - 遍历结束后，
k即为有效元素的数量，数组前k位就是结果。
为什么用范围 for？
传统写法需要手动管理索引，而 C++11 引入的范围 for 循环可以更简洁地遍历容器，代码可读性更高，且不易出错。在本题中，范围 for 可以完美替代传统索引遍历，实现极简代码。
三、代码实现（范围 for 版本）
class Solution { public: int removeElement(vector<int>& nums, int val) { int k = 0; // 慢指针，记录有效元素位置 // 范围for遍历所有元素 for (auto x : nums) { if (x != val) { nums[k++] = x; // 写入有效元素，指针后移 } } return k; // 返回有效元素数量 } };代码解析
- 参数传递：
vector<int>& nums是引用传递，保证函数内修改直接作用于原数组。 - 慢指针
k：初始为 0，每次遇到有效元素就写入当前位置，然后自增。 - 范围 for：
for (auto x : nums)会自动遍历nums中的每个元素，x是当前元素的拷贝（也可写auto& x避免拷贝，性能更优）。 - 原地修改：将不等于
val的元素依次写入数组前半部分，完成原地移除。 - 返回值：
k即为有效元素的数量，调用者可通过k截取结果。
四、原理解析：为什么返回 k 就够了？
很多同学会疑惑：函数只返回了 k，为什么评测机能拿到正确数组？
核心原因有两点：
- 原地修改：
nums是引用传递，函数内部已经把有效元素覆盖到了数组前k位。 - 约定返回值：
k告诉调用者「有效元素有多少个，都存在数组前半部分」，评测机会根据k截取前k个元素与预期结果对比。
以示例[3,2,2,3]为例：
- 遍历后数组变为
[2,2,3,3]，k=2。 - 评测机截取前 2 个元素
[2,2]，与预期一致，判定通过。
五、复杂度分析
- 时间复杂度：O (n)，仅遍历一次数组，所有操作均为常数级。
- 空间复杂度：O (1)，仅使用常数级额外空间，原地修改无额外内存开销。
性能优化：范围 for vs 传统 for
- 范围 for 代码更简洁，可读性更高，适合遍历容器场景。
- 底层实现与传统 for 一致，性能无差异，编译器会优化为等价的索引遍历。
- 若需避免元素拷贝，可使用
for (auto& x : nums)，效率更优。
六、拓展：首尾双指针优化（可选）
当val出现次数很少时，可使用首尾双指针进一步减少赋值操作：
class Solution { public: int removeElement(vector<int>& nums, int val) { int left = 0, right = nums.size(); while (left < right) { if (nums[left] == val) { nums[left] = nums[right - 1]; right--; } else { left++; } } return left; } };- 思路：左指针找
val，右指针找非val，交换两者，减少无效赋值。 - 时间复杂度仍为 O (n)，但赋值次数更少，适合
val稀疏场景。
七、总结
- 核心思想：双指针法实现原地移除，时间 / 空间复杂度最优。
- 代码极简：范围 for 让代码更简洁易读，适合日常开发。
- 关键理解：返回
k是有效元素计数，数组已在函数内原地修改，两者配合完成题目要求。
这道题是数组操作的基础入门题，掌握双指针思想和范围 for 的使用，对后续学习更复杂的数组 / 链表操作有很大帮助。