在Leetcode的经典150题中，有三道从有序数组中移除重复元素的题目，分别是移除指定元素、移除重复元素、移除重复元素但保留2个重复元素。
27. Remove Element
26. Remove Duplicates from Sorted Array
80. Remove Duplicates from Sorted Array II

不对题目进行追溯，重点对思路进行梳理和总结，并给出示例代码。

要求

1. 有序数组
2. 将满足条件的有效元素移动到数组的前部，空间复杂度O(1)
3. 返回有效元素数量

P27 移除指定元素

算法

1. 两个指针分别指向数组首尾（left, right）
2. 如果left指针指向为有效元素（不等于val），则向右移动
3. 如果left指针执行为无效数字（等于val），则right指针从尾部向左扫描，找到第一个有效元素，copy到left所指位置，right左移到下一个候选元素。
4. 当right指针移动到left左侧，扫描结束，right指向了最后一个有效元素

边界条件

1. 输入数组为空，直接返回0
2. 当left和right指向相同元素时，需要小心处理。如果该元素为有效元素，则left向右移动，此时right指向最后一个有效元素。
3. 如果该元素为无效元素，则right向左移动，有可能越界为负数，此时数组中没有有效元素。在最后返回时，需要特殊处理（直接+1也是可以的，明文处理更容易理解）。

示例代码

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        if (nums.size() == 0)
        {
            return 0;
        }

        int left = 0;
        int right = nums.size() - 1;
        while (left <= right)
        {
            // move to the next val position
            if (nums[left] != val)
            {
                ++left;
                continue;
            }
            // to find next non-val element
            if (nums[right] == val)
            {
                --right;
                continue;
            }
            // copy to left
            nums[left] = nums[right];
            ++left;
            --right;
        }
        return right >= 0 ? right + 1 : 0;
    }
};

P26 移除重复元素

算法

1. 快慢指针（为了和上面保持一致，统一叫做left和right），left 指针始终指向最后一个有效元素，right指向下一个需要处理的元素
2. 如果right指向的元素和left相同，则left保持不动，right向右移动一位
3. 如果right指向的元素和left不同，则将该元素指向left的下一个位置（left向右移动一位）。

边界条件

• 数组为空

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() == 0)
        {
            return 0;
        }
        int left = 0;
        int right = 0;
        for (; right < nums.size(); ++right)
        {
            if (nums[right] == nums[left])
            {
                continue;
            }
            nums[++left] = nums[right];
        }
        return left + 1;
    }
};

P80 移除重复元素，但是保留2个重复元素

常规算法
使用一个辅助变量（hitCnt），记录最近一个有效元素出现的次数，如果hitCnt大于2，则跳过

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() < 3)
        {
            return nums.size();
        }
        int left = 0;
        int right = 1;
        int hitCnt = 0;
        for (; right < nums.size(); ++right)
        {
            if (nums[left] != nums[right])
            {
                nums[++left] = nums[right];
                hitCnt = 0;
                continue;
            }
            ++hitCnt;
            if (hitCnt < 2)
            {
                nums[++left] = nums[right];
            }
        }
        return left + 1;
    }
};

更优算法（通用）
比较当前处理元素与有效元素中的倒数第2个元素（left - 1 指向的元素），如果相等，则跳过，如果不等于，则拷贝到有效元素中。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() < 3)
        {
            return nums.size();
        }
        int left = 1;
        int right = 2;
        while (right < nums.size())
        {
            if (nums[right] != nums[left - 1])
            {
                nums[++left] = nums[right];
            }
            ++right;
        }
        return left + 1;
    }
};