双指针 – 数组

数组的双指针一般分为两类：

• 1 快慢指针
• 2 左右指针：相向指针和同向指针包括滑动窗口。

1 快慢指针

快慢指针的常见用处是原地修改数组。

快慢指针的使用是有限制的，即数组必须有序，或者限定锚点值。

常见解题思路：

• 1 快指针寻找与慢指针处结果不同或者与标准结果不同的结果。
• 2 返回或者待处理的值是慢指针的位置。

经典题目：

• 1 删除有序数组中的重复项
• 2 删除排序链表中的重复元素
• 3 移除元素
• 4 移动零

经典模版：

int removeDuplicates(vector& nums) {
    if (nums.size() == 0) {
        return 0;
    }
    int slow = 0, fast = 0;
    while (fast < nums.size()) {
        if (nums[fast] != nums[slow]) {
            slow++;
            // 维护 nums[0..slow] 无重复
            nums[slow] = nums[fast];
        }
        fast++;
    }
    // 数组长度为索引 + 1
    return slow + 1;
}

2 左右指针

相向指针和同向指针（滑动窗口）具体可以见：双指针 – 相向/同向双指针

相向指针的经典题目：

• 1 两数之和，三数之和，四数之和。
• 2 二分查找。
• 3 反转数组，回文串判断，最长回文串。

同向指针的经典题目：

• 1 长度最小的子数组
• 2 乘积小于k的子数组
• 3 无重复字符的最长子串

滑动窗口的模版：

• 1 右移增大窗口
• 2 左移缩小窗口

/* 滑动窗口算法框架 */
void slidingWindow(string s) {
    unordered_map<char, int> window;

    int left = 0, right = 0;
    while (right < s.size()) {
        char c = s[right];
        // 右移（增大）窗口
        right++;
        // 进行窗口内数据的一系列更新

        while (window needs shrink) {
            char d = s[left];
            // 左移（缩小）窗口
            left++;
            // 进行窗口内数据的一系列更新
        }
    }
}