双指针的一个应用

Leetcode上的一个双指针题的解法与简化

题目：80. 删除有序数组中的重复项 II

题目链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/description/

给你一个有序数组nums，请你**原地** 删除重复出现的元素，使得出现次数超过两次的元素只出现两次，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

题解

读完题目之后，我们应该注意到：nums数组是有序的！这意味着：相同元素必然连续。

我们可以设置快慢两个指针：fast和slow，运用for循环进行遍历，判断哪些元素应该保留，哪些应该剔除。

具体而言，slow指针表示处理出的数组的长度，fast指针表示已经检查过的数组的长度。即nums[fast]表示待检查的第一个元素，nums[slow − 1]为上一个应该被保留的元素所移动到的指定位置。

因为本题要求相同元素最多出现两次，所以我们需要检查上上个应该被保留的元素nums[slow − 2]是否和当前待检查元素nums[fast]相同。当且仅当nums[slow − 2] == nums[fast]时，当前待检查元素nums[fast]不应该被保留（因为此时必然有nums[slow − 2] == nums[slow − 1] == nums[fast]）。

最后，slow即为处理好的数组的长度。

特别地，数组的前两个数必然可以被保留，因此对于长度不超过2的数组，我们无需进行任何处理，对于长度超过2的数组，我们直接将双指针的初始值设为2即可。

于是便有了这样的解答：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n <= 2) { // 特殊判断，如果nums长度小于2，直接输出长度n即可
            return n;
        }
        int slow = 2, fast = 2; // 因为上面已经做过特殊判别，所以这里快慢指针从2开始
        while (fast < n) {
            if (nums[slow - 2] != nums[fast]) { // 因为题目要求最多两个数相同，所以这么判断
            // 如果nums[slow - 2] == nums[fast]，代表已经有两个数相等，此时nums[fast]
            // 对应的数值不能放进结果之中。反之，如果nums[slow - 2] != nums[fast]，
            // 那么nums[fast]可以放进nums[slow]中，并且slow++，记录结果的长度。
                nums[slow] = nums[fast]; 
                slow++;
            }
            fast++; // 不管怎么样，快指针都是要向前遍历各个元素的
        }
        return slow; // 返回结果的长度，即slow
    }
};

优化

基于上面显式的双指针法，我们可以进一步抽象简化。

首先应该考虑，我们使用双指针的目的是什么？其实是方便指向我们要使用的数字。所以指针对应的数值才是主角。

在下面的题解中，我们应该尽量少使用指针，让数值自己出来比较：

联想到C++的for循环语法：for (int num : nums)，可以让num自身当右指针；

可以再令一个i代表左指针。

结合上面的思想，我们可以得到下面的代码：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i = 0; // 左指针初始化
        for (int num : nums) { // num当右指针
            if (i < 2 || nums[i - 2] < num) { // i < 2是特殊判断，nums[i - 2] < num
            // 是因为题目要求相同元素不能超过两个。之所以可以用小于号判断，是因为数组是有序的
                nums[i] = num; // 相当于上面官方解法的nums[slow] = nums[fast];
                i++; // 相当于上面官方解法的slow++;，即左指针移动
            }
        }
        return i; // 输出长度，即相当于上面题解的slow
    }
};

扩展

如果每个元素最多出现K次，你要怎么修改上面的代码？

很简单，改成if (i < k || nums[i - k] < num)就好了！

（这能不能看作这类问题的通解呢？）