时间轴

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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]的值。
    否则跳过。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    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;
        }
    };