删除有序数组中的重复项
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你一个 非严格递增排列 的数组 nums，请你原地删除重复出现的元素，使每个元素 只出现一次，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致。
考虑 nums 的唯一元素的数量为 k。去重后，返回唯一元素的数量 k。nums 的前 k 个元素应包含排序后的唯一数字，下标 k - 1 之后的剩余元素可以忽略。
示例 1
示例 2
模拟答题者思考
1. 我先想暴力：开一个新数组 res，从左到右扫 nums，遇到与 res 末尾不同的就 append——逻辑对，但用了 O(n) 额外空间，题目要求原地修改。
2. 重复在哪里？数组已排序，相同元素一定挨在一起。去重时只需关心「当前已写入的最后一个唯一值」，不必与前面所有元素逐一比较。
3. 双指针：用 slow 标记「去重结果区」的末尾，用 fast 从 1 开始扫描。若 nums[fast] != nums[slow]，说明遇到新唯一值，扩展结果区并写入。
4. 为什么只比 nums[slow]？有序性保证：若 nums[fast] 与 nums[slow] 相等，则 nums[fast] 一定是重复；若不等，则 nums[fast] 一定大于 nums[slow]，是新唯一值。
5. 最终 nums[0..slow] 即为去重结果，返回 slow + 1。每个元素最多被访问一次，时间 O(n)，仅用两个下标，空间 O(1)。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
slow | int | 定义：已写入去重结果区的最后一个唯一元素下标，即 nums[0..slow] 为当前已确认的唯一前缀维护：初始 slow = 0（第一个元素天然唯一）；每发现新值时先 slow++ 再写入更新：当 nums[fast] != nums[slow] 时，slow += 1; nums[slow] = nums[fast] |
fast | int | 定义：扫描指针，从 1 到 n-1 遍历整个数组维护：每次只与 nums[slow] 比较（有序数组下重复项必相邻，无需回看更早位置）更新：每轮循环末尾 fast++，直到遍历完所有元素 |
k（返回值） | int | 定义：去重后唯一元素个数 维护：等于 slow + 1（下标从 0 起，长度 = 最后下标 + 1）更新：循环结束后直接返回，无需额外计数器 |
落码步骤
1. 若 nums 为空，直接返回 0；否则令 slow = 0（nums[0] 作为第一个唯一元素）
2. for fast in range(1, len(nums))：若 nums[fast] != nums[slow]，则 slow += 1，nums[slow] = nums[fast]
3. 循环结束，nums[0..slow] 为去重后的唯一前缀
4. 返回 slow + 1 作为唯一元素个数 k
代码实现
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
slow = 0 # nums[0..slow] 为当前已确认的唯一前缀
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.empty()) return 0;
int slow = 0; // nums[0..slow] 为当前已确认的唯一前缀
for (int fast = 1; fast < nums.size(); fast++) {
if (nums[fast] != nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;
}
};
// 时间 O(n)，空间 O(1)复杂度分析
O(n)
O(1)
常见坑
返回值是 slow + 1 而不是 slow：下标从 0 开始，长度 = 最后下标 + 1。
写入顺序错误：应先 slow++ 再赋值 nums[slow] = nums[fast]，否则会覆盖尚未保留的唯一元素。
fast 应从 1 开始而非 0：nums[0] 已作为初始唯一元素，从 0 开始会把自己与自己比较，逻辑冗余且易错。
必测边界 Case
nums = [1] → 1, nums = [1]（无需去重，直接返回 1）
nums = [2,2,2,2] → 1, nums = [2,_,_,_]（fast 扫完无新值，slow 始终为 0）
nums = [1,2,3,4] → 4, nums = [1,2,3,4]（每个元素都被写入，slow 最终为 3）