双指针，数组去重

一、核心原理慢指针i指向去重后新数组的最后一个有效位置。快指针j遍历整个原数组寻找新的不重复元素。规则找到不重复元素 → 赋值给慢指针的下一位慢指针前进。找到重复元素 → 快指针直接跳过。二、场景 1有序数组去重保留一个重复元素题目要求给定升序有序数组原地删除重复元素使每个元素只出现一次返回新数组长度。示例[0,0,1,1,1,2,2,3,3,4]→ 去重后[0,1,2,3,4]返回长度 5。#include iostream #include vector using namespace std; ​ // 有序数组去重双指针核心函数 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 return slow 1; } ​ int main() { vectorint nums {0, 0, 1, 1, 1, 2, 2, 3, 3, 4}; int newLen removeDuplicates(nums); ​ cout 去重后数组长度 newLen endl; cout 去重后数组; for (int i 0; i newLen; i) { cout nums[i] ; } return 0; }三、场景 2有序数组去重保留最多两个重复元素题目要求每个元素最多出现 2 次LeetCode 80 经典题。示例[1,1,1,2,2,3]→[1,1,2,2,3]返回 5。int removeDuplicates2(vectorint nums) { if (nums.size() 2) return nums.size(); ​ int slow 1; // 允许前两个元素保留 for (int fast 2; fast nums.size(); fast) { // 核心和 slow-1 比较保证最多两个重复 if (nums[fast] ! nums[slow - 1]) { slow; nums[slow] nums[fast]; } } return slow 1; }四、场景 3无序数组去重双指针通用版无序数组不能直接比较相邻元素双指针 标记实现原地去重int removeDuplicatesUnordered(vectorint nums) { if (nums.empty()) return 0; ​ int slow 0; for (int fast 1; fast nums.size(); fast) { bool isDuplicate false; // 检查 fast 是否在 slow 前面已出现 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; }建议用哈希表实现O(n)时间int removeDuplicates(vectorint nums) { unordered_mapint, bool mp; int idx 0; ​ for (int x : nums) { //遍历数组 /vector 等容器不用写下标 if (!mp[x]) { mp[x] true; nums[idx] x; } } ​ nums.resize(idx); return idx; }五、总结慢指针slow 标记去重数组的最后位置快指针fast: 遍历数组寻找新元素O(n)时间 O(1)空间