【数组】【快慢双指针】删除有序数组中的重复项+移除元素+删除有序数组中的重复项II

今天趁热打铁，接着刷了几道标签是【数组】的题，基本都是双指针就能解决。

1、删除有序数组中的重复项

该题对应力扣网址

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i,j;
        int count = 0;
        int n = nums.size();
        nums.push_back(nums[n-1]);
        vector <int> nums1;
        for(i=0;i<n;i++){
            if(nums[i]==nums[i+1]){
                continue;
            }
            nums1[count] = nums[i];
            count++;
        }
        for(j=0;j<count;j++){
            nums[j]=nums1[j];
        }
        return count;
    }
};

搜了一下，原来vector是动态分布内存，在没有进行初始化之前不能使用下标的方式进行访问。改了之后就没问题了。

AC代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i,j;
        int count = 0;
        int n = nums.size();
        vector <int> nums1(n,0);
        for(i=0;i<n;i++){
            if(i!=0 && nums[i]==nums[i-1]){
                continue;
            }
            nums1[count] = nums[i];
            count++;
        }
        for(j=0;j<count;j++){
            nums[j]=nums1[j];
        }
        return count;
    }
};

我的思路是又开辟了一个新的vector，把筛选之后不重复的存到新vector里，最后吧新vector的值赋给旧vector。
看了题解之后才知道，直接用双指针做其实更方便，不过和之前三数之和双指针不一样的地方是，这里用的是移向同一方向的快慢指针。
具体方法在下面的题目中介绍。

2、移除元素

该题对应力扣网址

AC代码

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i,j;
        int n = nums.size();
        //快慢指针
        int first=0,low=0;
        while(first<n){
            if(nums[first]==val){
                first++;
                continue;
            }
            nums[low] = nums[first];
            low++;
            first++;
        }
        return low;
    }
};

这道题我就用了快慢双指针的思想，因为需要在原本数字的基础上进行修改，所以就需要first指针走快点进行比较，low指针走慢点进行修改。代码还是写的挺浅显易懂的就不赘述了。

3、删除有序数组中的重复项ii

该题对应力扣网址

AC代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i,j;
        int n = nums.size();
        //快慢指针
        int first=1,low=1;
        //计数器
        int count=1;
        while(first<n){
            if(nums[first]==nums[first-1]){
                count++;
                if(count<=2){
                    nums[low] = nums[first];
                    low++;
                }
                first++;
                continue;
            }
            count = 1;
            nums[low] = nums[first];
            low++;
            first++;
        }
        return low;
    }
};

跟上一个题的思路基本一致，不过写的时候，我也确实考虑到了能不能根据这个gap=2来想方法，不过使用的是count来计数。
去看了题解，它的方法更简洁巧妙，我写出来主要思想，大家就明白的差不多了，它的核心判断条件是nums[slow - 2] != nums[fast]。大家感兴趣的话可以移步去看详细代码。