算法系列：双指针

这几天接连遇到了一些双指针的问题，但是说实话，并没有从这些题中看到一种通用的东西，也就不是能很好的做一个总结，但不得不说双指针是一个很神奇的东西，所以做一道记一道吧。

快慢指针

快慢指针也是双指针，但是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止，如fast每次增长两个，slow每次增长一个。

常用于链表问题，如：slow开始移动，由于移动速度是 fast 的一半，那么 fast 移动到链表的末尾时，slow 就位于链表的中央，可以用这这种方法求链表的中点。

26. 删除有序数组中的重复项

给你一个升序排列的数组 nums，请你原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。元素的相对顺序应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组 nums 的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。将最终结果保存到 nums 的前 k 个位置后返回 k 。

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

这个题乍一看还真不会，于是果断看了题解：

• fast 和 slow 初始为 1，因为就算数组内全是重复元素，那么 1 也可以表示其中不重复的数量
• 如果 fast 和 fast-1 对应的元素相等，表示有重复元素，此时 fast++，继续搜索后面的元素
• 如果 fast 和 fast-1 不相等，表示没有重复元素，且，不重复的元素是 nums[fast]，此时我们让 nums[slow]=nums[fast]，slow 和 fast 同时向后移动即可

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int slow = 1, fast = 1;
        int n = nums.size();
        while (fast < n) {
            if (nums[fast] != nums[fast-1]) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
};

剑指 Offer II 022. 链表中环的入口节点

给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

首先明确一点，使用哈希存储地址肯定可以做出来，但这里是为了熟悉双指针。

• 假设 fast 指针和 slow 指针在紫色节点处相交
• 对于 fast 指针，走过的距离为 $a+n(b+c) + b$，$n$ 为任意整数
• 对于 slow 指针，走过的距离为 $a+m(b+c) + b$，$m$ 为任意整数

由于 fast 移动的距离是 slow 的二倍，因此：

\brgin{equation}
a+n(b+c)+b = 2 [a+m(b+c) + b] \\
\Rightarrow a = (n-2m)(b+c) - b
\end{equation}

也就是说，$a$ 的长度等于整数倍的环的长度减去 $b$ 的长度。得到这个等式后，我们让一个指针从 head 出发，slow 指针从相交处出发，两者相交时，就是环的入口节点。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast != nullptr) {
            slow = slow->next;
            if (fast->next == nullptr) {
                return nullptr;
            }
            fast = fast->next->next;
            if (fast == slow) {
                ListNode *ptr = head;
                while (ptr != slow) {
                    ptr = ptr->next;
                    slow = slow->next;
                }
                return ptr;
            }
        }
        return nullptr;
    }
};

对撞指针

对撞数组适用于有序数组、利用数组两侧求最值、只用数组内的两个元素等问题，应该第一时间想到用对撞指针解题。

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

• 双指针，左指针位于左侧，右指针位于右侧，求一次能存储的最大水量
• 如果左边低，为了能求存储的最大水量，就需要将左指针向右移动，同理，如果右边低，就需要将右指针向左移动
• 每次移动的时候求极值就可以了

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int l = 0, r = n - 1;
        int res = 0;
        while (l < r) {
            int t1 = height[l];
            int t2 = height[r];
            res = max(res, min(t1, t2) * (r - l));
            if (t1 < t2) {
                l++;
            } else {
                r--;
            }
        }
        return res;
    }
};

881. 救生艇

给定数组 people 。people[i] 表示第 i 个人的体重，船的数量不限，每艘船可以承载的最大重量为 limit。每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。返回承载所有人所需的最小船数。示例：

输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)

我们假设一种极端情况，数组排序后是 [1, 2, ..., n-2, n-1]，而船能容纳的极限是 n。那么，最佳分配就是让 1 和 n-1 在一起，2 和 n-2 在一起。此时只用两条船。虽然 1 可以和 2 在一起，那么要承载 n-2 和 n-1，就需要 3 条船。

基于贪心的思想，我们应该尽可能的把轻的和重的分配到一起，来减少船的使用数量，首先对数组排序：

• 设立双指针，l=0, r=n-1
• 因为船只能坐两个人，因此，如果 nums[l] + nums[n-1] <= limit，就让这两个人坐一起，此时 l++
• 而无论如何，都需要 r--，因为数组末尾的必须上一个人，而数组左侧的人选择性上或不上

class Solution {
public:
    int numRescueBoats(vector<int> &people, int limit) {
        int ans = 0;
        sort(people.begin(), people.end());
        int light = 0, heavy = people.size() - 1;
        while (light <= heavy) {
            if (people[light] + people[heavy] <= limit) {
                ++light;
            } 
            --heavy;
            ++ans;
        }
        return ans;
    }
};

红白球

给定一个长度为 $n$ 的字符串，其中，W 表示白色的球，R 表示红色的球，如果把红色的球放到一起，请问最少移动多少次？示例：

输入：s = "WRRWRW"
输出：1
输入：s = "WWRWWWRWR"
输出：4，"WWRWWWRWR" -> "WWWRWWRWR" -> "WWWWRWRWR" -> "WWWWWRRWR" -> "WWWWWWRRRW"

一个很经典的双指针题目，注：2022年微软秋招笔试题原题。这个题解有点长，日后完善。

class solution{
    int num(string& s) {
        int red_count = 0;
        for (char c : s) {
            if (c == 'R') red_count++;
        }
        int left = 0, right = s.size() - 1, result = 0;
        while (left < right) {
            if (s[left] == 'R' && s[right] == 'R') {
                red_count -= 2;
                result = right - left - 1 - red_count;
                ++left;
                --right;
            } else if (s[left] != 'R') {
                left++;
            } else {
                right--;
            }
        }
        return result;
    }
};