双指针概述

用法

• 对于一个序列，用两个指针维护一段区间。例如：快排，最大不重复子区间长度
• 对于两个序列，两个指针各自指向这两个序列中的一个，用这两个指针维护某种次序。例如：归并排序。

模板

第一类：

int j = 0;
for (int i = 0; i < n; i++)
{
    while (j <= i && check(i, j)) {
        j++;
    }
    //具体问题逻辑
}

第二类：

int i = 0, j = 0;
while (i < n && j < m) {
    //具体问题逻辑
}

例题：

题目描述：
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

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

示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：
0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列

思路：
典型的双指针问题。
i指向的位置表示当前元素是否需要保留
j指向的位置表示当前转移元素即将被存放的地方
需要遍历一遍数组，i指向的元素是否需要转移到j需满足的性质有两点：

• i < 1时可以转移，因为只有一个元素，肯定没有重复
• i指向的元素与j-1的指向的元素不相同，说明可以转移

上代码：

class Solution {
    public int removeDuplicates(int[] nums) {
        //之前的写法，不够系统，每次都是瞎写
        // if (nums == null) {
        //     return 0;
        // }
        // int n = nums.length;
        // if (n <= 1) {
        //     return n;
        // }
        // int slow = 1, fast = 1;
        // while (fast < n) {
        //     if (nums[slow - 1] != nums[fast]) {
        //         nums[slow] = nums[fast];
        //         slow++;
        //     }
        //     fast++;
        // }
        // return slow;
        //使用模板，思路清晰
        if (nums == null) return 0;
        int n = nums.length;
        if (n <= 1) return n;
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (i == 0 || nums[i] != nums[i-1]) {
                nums[j] = nums[i];
                j++;
            }
        }
        return j;
    }
}

题目描述：
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1：
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。

示例 2：
输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素

提示：
0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列

思路：
相较于26，仅有一处不同，即每个元素最多出现1次改为每个元素最多出现两次。

• i`` < 2的元素都可以转移，因为最多不超过两个元素，重复次数肯定不会超过两次
• i指向的元素与j-2的指向的元素不相同，说明可以转移

上代码：

class Solution {
    public int removeDuplicates(int[] nums) {
        // if (nums == null) {
        //     return 0;
        // }
        // int n = nums.length;
        // if (n <= 2) {
        //     return n;
        // }
        // int s = 2, f = 2;
        // while (f < n) {
        //     if (nums[s-2] != nums[f]) {
        //         nums[s] = nums[f];
        //         s++;
        //     }
        //     f++;
        // }
        // return s;
        if (nums == null) return 0;
        int n = nums.length;
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (i < 2 || nums[i] != nums[j - 2]) {
                nums[j++] = nums[i];
            }
        }
        return j;
    }
}

总结：数组中每个元素的个数最多不超过K次的模板

public int removeDuplicates(int[] nums) {
     if (nums == null) return 0;
    int j = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i < K || nums[i] != nums[j - K]) {
            nums[j++] = nums[i];
        }
    }
    return j;
}