面试经典150题 P80 删除有序数组中的重复项 II

---

时间轴

时间轴

2025-09-29

init

双指针

---

题目：

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

https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/description/?envType=study-plan-v2&envId=top-interview-150

这种简单直接的方法还是可以过的，但是效率很低很低，几乎是擦边过。

#include <algorithm>
#include <vector>
using std::vector;

class Solution {
public:
  int removeDuplicates(vector<int> &nums) {
    int i, n;
    n = nums.size();
    i = 0;

    while (i < nums.size()) {
      if (i >= 2 && nums[i] == nums[i - 1] && nums[i - 1] == nums[i - 2]) {
        nums.erase(nums.begin() + i);
      } else {
        i++;
      }
    }

    return nums.size();
  }
};

采用双指针方法更为高效(快慢指针)，在原数组上“覆盖掉”多余的元素。

• 慢指针（slow）：指向当前结果数组的末尾。
• 快指针（fast）：遍历整个数组。
  • 如果 slow < 2，直接保留（因为前两个元素无论如何都要保留）。
  • 如果 nums[fast] != nums[slow - 2]，说明新数字还没超过 2 次， 覆盖 num[slow]的值。
  • 否则跳过。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n <= 2) {
            return n;
        }
        int slow = 2, fast = 2;
        while (fast < n) {
            if (nums[slow - 2] != nums[fast]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
};