双指针法秒杀数组去重：3大场景最优解

数组去重是算法面试、笔试的高频考点，双指针法是解决这类问题的最优解之一——O (n) 时间复杂度、O (1) 原地空间，无需额外开辟大数组，高效又简洁。

本文用一句话核心原理+3 大经典场景（有序留 1 个、有序留 2 个、无序去重），带你彻底掌握双指针数组去重，代码可直接复制运行、刷题使用。

一、核心原理（一句话死记硬背）

双指针法的灵魂就是快慢指针分工协作：

1. 慢指针（slow）：专属定位→指向去重后新数组的最后一个有效元素下标，决定新数组的长度。
2. 快指针（fast）：专属遍历→从头到尾扫描原数组，寻找不重复的新元素。
3. 核心规则：
   • 快指针找到不重复元素→慢指针前进一步，把新元素赋值给慢指针位置；
   • 快指针找到重复元素→直接跳过，继续遍历。

一句话总结：慢指针守新数组，快指针找新元素。

二、场景 1：有序数组去重（每个元素只保留 1 个）

题目要求

给定升序有序数组，原地删除重复元素，使每个元素只出现一次，返回去重后新数组的长度。

示例：输入[0,0,1,1,1,2,2,3,3,4]→ 输出[0,1,2,3,4]，返回长度5。

解题思路

因为数组有序，重复元素一定相邻，直接比较nums[fast]和nums[slow]即可判断是否重复。

• 慢指针初始指向第一个元素（新数组起点）；
• 快指针从第二个元素开始遍历；
• 不重复则更新慢指针，重复则快指针跳过。

完整可运行代码（C++）

c++

#include <iostream> #include <vector> using namespace std; // 有序数组去重（保留1个重复元素）- 双指针核心函数 int removeDuplicates(vector<int>& nums) { // 边界处理：空数组直接返回0 if (nums.empty()) return 0; int slow = 0; // 慢指针：指向新数组最后一个有效位置 // 快指针：遍历整个数组，寻找不重复元素 for (int fast = 1; fast < nums.size(); fast++) { // 找到不重复元素 if (nums[fast] != nums[slow]) { slow++; // 慢指针前进一位 nums[slow] = nums[fast]; // 覆盖更新，写入新数组 } // 重复元素：快指针自动++，无需任何操作 } // 新数组长度 = 慢指针下标 + 1（下标从0开始） return slow + 1; } // 测试主函数 int main() { vector<int> nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4}; // 获取去重后的数组长度 int newLength = removeDuplicates(nums); cout << "去重后数组长度：" << newLength << endl; cout << "去重后数组："; // 遍历输出前newLength个元素（即去重后的有效数组） for (int i = 0; i < newLength; i++) { cout << nums[i] << " "; } return 0; }

输出结果

去重后数组长度：5 去重后数组：0 1 2 3 4

三、场景 2：有序数组去重（每个元素最多保留 2 个）

题目要求（LeetCode 80 经典题）

给定升序有序数组，原地删除重复元素，使每个元素最多出现 2 次，返回新数组长度。

示例：输入[1,1,1,2,2,3]→ 输出[1,1,2,2,3]，返回长度5。

解题思路

有序数组 + 最多保留 2 个重复，核心逻辑：快指针元素 与 慢指针前 1 位元素比较（保证不超过 2 个重复）。

• 数组长度≤2 时，直接返回原长度（无需去重）；
• 慢指针初始指向第 2 个元素（下标 1），快指针从第 3 个元素（下标 2）开始遍历；
• 不重复则更新慢指针，重复则跳过。

核心代码

c++

// 有序数组去重（最多保留2个重复元素） int removeDuplicates2(vector<int>& nums) { // 边界：数组长度≤2，直接返回原长度 if (nums.size() <= 2) return nums.size(); int slow = 1; // 慢指针初始指向第2个元素（允许前两个保留） // 快指针从第3个元素开始遍历 for (int fast = 2; fast < nums.size(); fast++) { // 核心：和slow-1比较，保证最多2个重复 if (nums[fast] != nums[slow - 1]) { slow++; nums[slow] = nums[fast]; } } return slow + 1; }

测试验证

输入[1,1,1,2,2,3]，调用函数返回5，去重后数组为[1,1,2,2,3]，完美符合要求。

四、场景 3：无序数组去重（双指针通用版）

题目要求

数组无序，原地删除重复元素，每个元素只保留 1 个，返回新数组长度。

解题思路

无序数组的重复元素不相邻，无法直接比较快慢指针，需要：

1. 快指针遍历元素；
2. 内层循环检查该元素是否已在慢指针前面的新数组中出现；
3. 未出现则加入新数组，重复则跳过。

优化建议：双指针 + 内层检查时间复杂度为 O (n²)，实际开发 / 刷题优先用哈希表（O (n) 时间，更高效）。

方案 1：双指针原地去重（O (n²) 时间）

// 无序数组去重 - 双指针通用版（原地操作） int removeDuplicatesUnordered(vector<int>& nums) { if (nums.empty()) return 0; int slow = 0; // 慢指针：新数组最后位置 for (int fast = 1; fast < nums.size(); fast++) { bool isDuplicate = false; // 检查fast元素是否在新数组中已存在 for (int k = 0; k <= slow; k++) { if (nums[fast] == nums[k]) { isDuplicate = true; break; } } // 不重复则加入新数组 if (!isDuplicate) { slow++; nums[slow] = nums[fast]; } } return slow + 1; }

方案 2：哈希表优化（O (n) 时间，推荐）

// 无序数组去重 - 哈希表优化版（高效O(n)） int removeDuplicatesHash(vector<int>& nums) { unordered_map<int, bool> exist; // 标记元素是否已出现 int idx = 0; // 新数组下标 // 遍历原数组 for (int num : nums) { // 元素未出现过 if (!exist[num]) { exist[num] = true; // 标记为已出现 nums[idx++] = num; // 写入新数组 } } nums.resize(idx); // 截断数组，保留有效元素 return idx; }

五、终极总结（面试必背）

1. 双指针核心分工

• 慢指针（slow）：标记去重后新数组的最后一个有效位置；
• 快指针（fast）：遍历原数组，寻找不重复的新元素。

2. 三大场景对比

表格

3. 关键结论

1. 有序数组去重：无脑用双指针，最优解（O (n)+O (1)）；
2. 无序数组去重：优先用哈希表（时间最优），要求原地则用双指针 + 内层检查；
3. 所有场景均为原地修改数组，无需额外开辟新数组，空间效率拉满。

结语

双指针法是数组、链表类题目的万能技巧，吃透本文的去重场景，能快速迁移到移动零、合并两个有序数组、三数之和等高频题型。