前言

「原地删除有序数组中的重复项」是 LeetCode 26 题。给定一个按非递减顺序排列的数组，要求在每个元素最多保留一次的前提下，把去重后的元素放到数组前部，返回新的长度 k。判题系统只检查前 k 个元素，k 之后的内容不参与比较，但要求不能使用额外的数组空间。

这道题的「有序」是解题的关键。数组有序意味着相同的值一定相邻，因此不需要哈希表记录「见过谁」，只需要比较当前元素和前一个保留下来的元素。如果数组无序，原地去重在不排序的前提下无法用 O(1) 额外空间完成——这是题目给有序条件的原因。

常见错误有三类：用std::set或额外数组，虽然结果对但违反空间要求；在循环里反复erase，每次搬移尾部，整体退化成 O(n²)；返回nums.size()而不是新的长度，或者覆盖时读写指针的边界写错。本文给出快慢指针、std::unique和泛型写法三种实现，并说明它们的关系。

一、约束与返回值的含义

LeetCode 的函数签名是：

// 适用于 C++17
int removeDuplicates(std::vector<int>& nums);

返回值 k 表示去重后元素个数。判题系统会用 k 截取前 k 个元素，再与期望数组比较。因此函数必须保证：

1. 
   
2. 前 k 个位置存放的是去重后的元素，且保持原顺序；
3. 
   
4. k 之后的元素是什么无所谓，但不能越界写；
5. 
   
6. 额外空间是 O(1)，不能新建一个等长数组。
7. 
   

第 3 条是「原地」的含义。用std::vector<int> out;存结果再拷回去，空间是 O(n)，不符合要求；用std::set更糟，既费空间又丢了有序性带来的线性时间。

二、方法一：快慢指针

维护两个下标：slow指向「已写入的最后一个位置」，fast从头遍历。因为数组有序，只需比较nums[fast]和nums[slow]：不同就说明遇到了新值，把它写到slow + 1，并推进slow。

// 适用于 C++17
#include <cstddef>
#include <vector>

int removeDuplicates(std::vector<int>& nums) {
if (nums.empty()) return 0;

std::size_t slow = 0; // 最后一个已保留元素的下标
for (std::size_t fast = 1; fast < nums.size(); ++fast) {
if (nums[fast] != nums[slow]) {
++slow;
nums[slow] = nums[fast]; // 覆盖到前部
}
}
return static_cast<int>(slow + 1);
}

以[1, 1, 2, 3, 3]为例：

最终slow = 2，返回 3，前三个元素是[1, 2, 3]。时间复杂度 O(n)，每个元素读一次；空间 O(1)。fast从 1 开始，是因为第一个元素必然保留。

返回类型是int，而slow + 1是std::size_t，需要显式转换。题目保证数组长度在int范围内，转换安全；但在通用代码里，应确认这个前提。

三、方法二：std::unique

std::unique(first, last)把相邻的重复元素「移走」，保留每段重复的第一个，返回新的逻辑结尾。它同样是原地操作，不改变容器大小：

// 适用于 C++17
#include <algorithm>
#include <iterator>
#include <vector>

int removeDuplicatesUnique(std::vector<int>& nums) {
const auto new_end = std::unique(nums.begin(), nums.end());
return static_cast<int>(std::distance(nums.begin(), new_end));
}

std::unique的语义是「删除相邻重复」，对有序数组而言，所有重复都相邻，效果就是全局去重。若数组无序，它只会删掉连续出现的重复值，结果不是去重。这一点必须和std::remove区分：后者按值删除，前者按相邻相等删除。

std::distance对随机访问迭代器是 O(1)，返回difference_type（有符号）。转换成int前要确认长度范围。

这个方法代码最短，语义最清晰，前提是允许使用标准算法。面试若要求手写，仍然要会快慢指针版本。

四、方法三：泛型写法

把元素类型和比较方式抽出来，可以写成模板，适用于std::string、自定义结构体等：

// 适用于 C++17
#include <cstddef>
#include <functional>
#include <utility>
#include <vector>

template <typename T, typename Equal = std::equal_to<T>>
std::size_t uniqueInPlace(std::vector<T>& data, Equal eq = Equal{}) {
if (data.empty()) return 0;
std::size_t write = 0;
for (std::size_t read = 1; read < data.size(); ++read) {
if (!eq(data[read], data[write])) {
++write;
data[write] = std::move(data[read]);
}
}
return write + 1;
}

这里用std::move把元素移到前部，对std::string这类持有堆内存的类型可以避免一次深拷贝。移动之后data[read]处于有效但未指定状态，后续不会再读它，所以安全。write始终小于等于read，覆盖不会破坏尚未读取的元素。

三种方法的对比如下：

五、完整示例

// 适用于 C++17
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

int removeDuplicates(std::vector<int>& nums) {
if (nums.empty()) return 0;
std::size_t slow = 0;
for (std::size_t fast = 1; fast < nums.size(); ++fast) {
if (nums[fast] != nums[slow]) {
++slow;
nums[slow] = nums[fast];
}
}
return static_cast<int>(slow + 1);
}

void show(const std::vector<int>& nums, int k) {
std::cout << "k=" << k << " [";
for (int i = 0; i < k; ++i) {
if (i != 0) std::cout << ',';
std::cout << nums[static_cast<std::size_t>(i)];
}
std::cout << "]\n";
}

int main() {
std::vector<int> a{1, 1, 2};
const int ka = removeDuplicates(a);
show(a, ka); // k=2 [1,2]

std::vector<int> b{0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
const int kb = removeDuplicates(b);
show(b, kb); // k=5 [0,1,2,3,4]

std::vector<int> c;
const int kc = removeDuplicates(c);
show(c, kc); // k=0 []
return 0;
}

按标准语义，输出依次是k=2 [1,2]、k=5 [0,1,2,3,4]、k=0 []。空数组时函数直接返回 0，不会访问nums[0]。对于 k 之后的残留元素，示例没有清理，也不应该依赖它们的值。

常见坑点

1. 返回原数组长度

❌return static_cast<int>(nums.size());—— 返回的是去重前的长度，判题系统会多比较重复元素。

✅ 返回slow + 1（或std::unique与begin()的距离）。

2. 空数组访问首元素

❌std::size_t slow = 0;后直接读nums[slow]，不判空 —— 空数组时越界。

✅ 函数开头if (nums.empty()) return 0;。

3. 循环内反复 erase

❌for (i = 1; i < nums.size(); ++i) if (nums[i] == nums[i-1]) nums.erase(nums.begin()+i);—— 每次搬移尾部，整体 O(n²)，且删除后下标错位。

✅ 用快慢指针一次遍历覆盖，最后不需要真的删除尾部。

4. 读写指针含义混淆

❌ 用nums[fast] != nums[fast-1]判断后写入nums[fast]—— 写回原位，等于没覆盖。

✅ 写指针用slow，读指针用fast，比较对象是nums[slow]（最后一个保留值）。

5. 用std::set去重

❌std::set<int> s(nums.begin(), nums.end());再拷回 —— 额外 O(n) 空间，违反原地要求。

✅ 利用有序性用双指针；空间 O(1)。

6. 以为std::unique能处理无序数组

❌ 对[1,2,1]调用std::unique后认为得到[1,2]—— 实际仍是[1,2,1]，因为它只删相邻重复。

✅ 先排序再用unique，或改用哈希集合（但那就不是原地了）。

7. 返回 k 但前 k 个未按顺序排列

❌ 用「把重复项交换到末尾」的写法，导致前 k 个元素顺序错乱。

✅ 快慢指针覆盖保持原相对顺序；判题系统按顺序比较。

8. 有符号与无符号混用

❌for (int i = 1; i < nums.size(); ++i)——int与size_t比较触发符号警告，极大长度下可能出错。

✅ 下标统一用std::size_t，返回时再显式转int。

总结

这道题是「双指针」最纯粹的形式：一个指针读、一个指针写，读指针永远不落后于写指针。理解这一点，就不会写出「删除后下标错位」或「反复 erase」的版本。有序条件不是装饰，它把「判断是否重复」从「查表」降成了「看前一个元素」，这才是 O(1) 空间解法成立的根本原因。