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

数组去重是算法面试、笔试的高频考点双指针法是解决这类问题的最优解之一——O (n) 时间复杂度、O (1) 原地空间无需额外开辟大数组高效又简洁。本文用一句话核心原理3 大经典场景有序留 1 个、有序留 2 个、无序去重带你彻底掌握双指针数组去重代码可直接复制运行、刷题使用。一、核心原理一句话死记硬背双指针法的灵魂就是快慢指针分工协作慢指针slow专属定位→指向去重后新数组的最后一个有效元素下标决定新数组的长度。快指针fast专属遍历→从头到尾扫描原数组寻找不重复的新元素。核心规则快指针找到不重复元素→慢指针前进一步把新元素赋值给慢指针位置快指针找到重复元素→直接跳过继续遍历。一句话总结慢指针守新数组快指针找新元素。二、场景 1有序数组去重每个元素只保留 1 个题目要求给定升序有序数组原地删除重复元素使每个元素只出现一次返回去重后新数组的长度。示例输入[0,0,1,1,1,2,2,3,3,4]→ 输出[0,1,2,3,4]返回长度5。解题思路因为数组有序重复元素一定相邻直接比较nums[fast]和nums[slow]即可判断是否重复。慢指针初始指向第一个元素新数组起点快指针从第二个元素开始遍历不重复则更新慢指针重复则快指针跳过。完整可运行代码Cc#include iostream #include vector using namespace std; // 有序数组去重保留1个重复元素- 双指针核心函数 int removeDuplicates(vectorint 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() { vectorint 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(vectorint 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 个返回新数组长度。解题思路无序数组的重复元素不相邻无法直接比较快慢指针需要快指针遍历元素内层循环检查该元素是否已在慢指针前面的新数组中出现未出现则加入新数组重复则跳过。优化建议双指针 内层检查时间复杂度为 O (n²)实际开发 / 刷题优先用哈希表O (n) 时间更高效。方案 1双指针原地去重O (n²) 时间// 无序数组去重 - 双指针通用版原地操作 int removeDuplicatesUnordered(vectorint 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(vectorint nums) { unordered_mapint, 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. 三大场景对比表格场景数组特点核心判断时间复杂度空间复杂度有序留 1 个升序 / 降序nums[fast] ! nums[slow]O(n)O(1)有序留 2 个升序 / 降序nums[fast] ! nums[slow-1]O(n)O(1)无序去重无顺序内层遍历检查 / 哈希表O(n²)/O(n)O(1)/O(n)3. 关键结论有序数组去重无脑用双指针最优解O (n)O (1)无序数组去重优先用哈希表时间最优要求原地则用双指针 内层检查所有场景均为原地修改数组无需额外开辟新数组空间效率拉满。结语双指针法是数组、链表类题目的万能技巧吃透本文的去重场景能快速迁移到移动零、合并两个有序数组、三数之和等高频题型。