力扣面试经典——80题

💡 参考代码：

/**
 * 删除有序数组中的重复项（最多保留2个相同元素）
 * 
 * @param nums 有序数组指针，用于原地删除重复元素
 * @param numsSize 数组长度
 * @return 返回删除重复元素后数组的新长度
 * 
 * @description 使用双指针法原地删除重复元素，使得每个元素最多出现两次
 * 时间复杂度: O(n) - 只需遍历数组一次
 * 空间复杂度: O(1) - 只使用常数额外空间
 * 
 */
int removeDuplicates(int* nums, int numsSize) {
    // 边界条件：如果数组长度小于等于2，无需处理直接返回
    // 因为最多保留2个相同元素，所以长度小于等于2的数组肯定符合要求
    if (numsSize <= 2) {
        return numsSize;
    }
    
    // 初始化慢指针指向索引2
    // 前两个元素肯定可以保留（最多允许2个重复），所以从第3个位置开始放置有效元素
    int slow = 2;
    
    // 快指针从索引2开始遍历整个数组
    // 从第3个元素开始检查是否需要保留
    for (int fast = 2; fast < numsSize; fast++) {
        // 核心判断条件：只有当当前元素与slow指针前两个位置的元素不同时才保留
        // 这确保了任何元素都不会出现超过2次
        // 原理：如果nums[fast] == nums[slow-2]，说明包括即将插入的位置已经有3个相同元素了
        if (nums[fast] != nums[slow - 2]) {
            // 将当前元素复制到slow指针位置
            nums[slow] = nums[fast];
            // 慢指针前移，指向下一个可放置元素的位置
            slow++;
        }
        // 如果nums[fast] == nums[slow-2]，则跳过当前元素（不复制），fast继续前进
    }
    
    // 返回新数组的长度
    // 由于slow指向下一个可放置位置的索引，所以直接返回slow即为数组长度
    return slow;
}

📖 总结：

点击展开题目总结

🤔 删除有序数组中的重复项 II

---

1️⃣ 题目核心信息

🎯 功能描述：原地删除有序数组中的重复元素，使得每个元素最多出现两次

📥 输入输出：

• 输入：有序数组 nums、数组长度 numsSize
• 输出：删除重复元素后数组的新长度，并修改原数组前k个元素

---

2️⃣ 实现原理

💡 核心思路：使用双指针技术，通过比较当前元素与已保留元素中倒数第2个元素来判断是否允许插入

📋 实现步骤：

1. 处理边界情况：数组长度≤2时直接返回
2. 初始化慢指针指向索引2（前两个元素肯定可以保留）
3. 快指针从索引2开始遍历数组
4. 当快指针元素与慢指针前两个位置元素不同时，将其复制到慢指针位置
5. 返回慢指针位置作为新数组长度

---

3️⃣ 关键点解析

初始思路 vs 最优解

💭 我的初始想法

使用显式计数器记录当前元素出现次数，当元素相同时只有计数小于1时才允许复制：

int removeDuplicates(int* nums, int numsSize) {
    int slow = 0;
    int count = 0;
    
    for (int fast = 1; fast < numsSize; fast++) {
        if (nums[fast] != nums[slow]) {
            nums[++slow] = nums[fast];
            count = 0;
        } else if(count < 1){
            count++;
            nums[++slow] = nums[fast];    
        }
    }
    
    return slow + 1;
}

⚡ 最优解法（隐式计数）

int removeDuplicates(int* nums, int numsSize) {
    if (numsSize <= 2) {
        return numsSize;
    }
    
    int slow = 2;
    
    for (int fast = 2; fast < numsSize; fast++) {
        if (nums[fast] != nums[slow - 2]) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    
    return slow;
}

🆚 对比分析

方面	初始思路	最优解
计数方式	显式计数器	隐式通过数组位置关系
代码复杂度	需要维护count变量	无需额外变量
可读性	逻辑清晰但稍复杂	简洁但需要理解技巧
扩展性	容易扩展到k次重复	需要修改索引计算

🎯 代码技巧

• 双指针法的经典应用
• 利用数组有序特性，通过位置关系隐式计数
• 边界条件的巧妙处理（前两个元素天然满足条件）

4️⃣ 使用场景

✅ 适用情况：

• 有序数组中限制元素出现次数
• 需要原地处理数组数据
• 类似问题：删除重复元素I、移除元素等

⚠️ 前提条件：

• 数组必须是排序的
• 只关心前k个元素，其余位置内容无关紧要

5️⃣ 复杂度分析

• ⏱️ 时间复杂度：O(n)，只需要遍历数组一次

• 💾 空间复杂度：O(1)，只使用了常数个额外变量

6️⃣ 注意事项

🚩 边界情况：

• 空数组或单元素数组：numsSize <= 2
• 所有元素都相同
• 所有元素都不相同
• 只有部分元素重复超过两次

💥 易错点：

• 忘记处理边界条件
• 慢指针起始位置应该是2而不是0
• 返回值应该是 slow 而不是 slow + 1
• 比较条件应该是 nums[fast] != nums[slow - 2] 而不是其他位置

加载评论中...