双指针算法详解：从原理到实战

1. 初始化两个指针：cur 指向数组首元素，dest（原 prev）初始化为 -1。
2. 遍历过程中：
   • 当 cur 遇到非零元素时，dest 右移一位并与 cur 交换元素。
   • 否则 cur 继续右移。
3. 重复上述过程直至 cur 到达数组末尾。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for (int cur = 0, dest = -1; cur < nums.size(); cur++) {
            if (nums[cur]) swap(nums[++dest], nums[cur]);
        }
    }
};

复写零

处理复写零问题的关键在于确定结束位置。由于是原地操作，直接正向遍历会导致覆盖未处理的数据，因此采用逆向复写策略。

1. 初始化指针：将 cur 和 dest 都指向数组首元素，然后 cur 开始移动。
2. 遍历规则：
   • 当 cur 指向 0 时：dest 移动两步。
   • 当 cur 指向非零元素时：dest 移动一步。
3. 终止条件：当 dest 到达数组末尾时停止。
4. 边界处理：若 cur 指向最后一个元素为 0 时，dest 可能越界。此时需要将 dest 回退两位，并将末尾元素置零，同时 cur 回退一位。
5. 逆向复写：由于已精确计算复写元素数量，无需担心原地复写导致的覆盖问题。

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur = 0, dest = -1, n = arr.size();
        // 双指针找最后一个复写的数
        while (true) {
            if (arr[cur] == 0) dest++;
            dest++;
            if (dest >= n - 1) break;
            cur++;
        }
        
        // 处理特殊情况
        if (dest == arr.size()) {
            cur--;
            dest -= 2;
            arr[arr.size() - 1] = 0;
        }
        
        // 从后向前复写
        while (cur >= 0) {
            if (arr[cur] == 0) arr[dest--] = arr[cur];
            arr[dest--] = arr[cur];
            cur--;
        }
    }
};

首尾双指针

首尾分别设定指针，可以交换元素解决移动零类似问题；也可以利用单调性解决其他问题。

移动零（不保持顺序）

如果不需要保持元素的先后顺序，也可以使用首尾双指针法，效率更高。

1. 设置左右指针，left 和 right。
2. left 找 0，right 找非零元素，交换。
3. 直到左右指针相遇。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            if (nums[left]) left++;
            if (nums[right] == 0) right--;
            if (left < right && nums[left] == 0 && nums[right] != 0)
                swap(nums[left], nums[right]);
        }
    }
};

盛水最多的容器

本题可以使用暴力解法，但双指针能显著优化。

根据体积计算公式 $V = w \times h$：宽度 $w$ 必定随着指针向内移动而减小，高度 $h$ 取决于较短的一边。

1. 首尾设定指针，向内移动。
2. 计算出当前体积后，将二者高度较小的一方排除，向内移动。因为无论移动哪一边，宽度都在减小，只有移动短边才有可能获得更大的面积。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = height.size() - 1;
        int v = 0;
        while (left < right) {
            int width = right - left;
            int high = min(height[left], height[right]);
            int vv = width * high;
            if (vv > v) v = vv;
            
            if (height[left] < height[right]) left++;
            else right--;
        }
        return v;
    }
};

两数之和（有序数组）

对于已排序的数组，可以使用双指针替代哈希表或暴力枚举。

1. 依旧设定首尾指针。
2. 存在以下规律：
   • 如果两指针所指元素之和小于目标值：变小一定得不到目标值，所以左指针右移。
   • 如果两指针所指元素之和大于目标值：变大一定得不到目标值，所以右指针左移。
3. 遍历直到找到和为目标值的两个数。

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int left = 0, right = price.size() - 1;
        while (left < right) {
            if (price[left] + price[right] > target) right--;
            else if (price[left] + price[right] < target) left++;
            else return {price[left], price[right]};
        }
        return {};
    }
};

三数之和

三数之和实际上是两数之和的变式。核心思路是固定一个数，然后在剩余部分使用双指针寻找另外两个数。

1. 先排序，然后固定其中一个数字，依次顺序固定，跳过重复元素。
2. 用两数之和类似的双指针法，计算三数之和是否为结果。
3. 需要注意的是，找到结果后要跳过重复元素，避免结果集重复。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> res;
        // 利用单调性，定尾部，前面走双指针
        for (int i = n - 1; i >= 2; i--) {
            if (i < n - 1 && nums[i] == nums[i + 1]) continue;
            int left = 0, right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] + nums[i] > 0) right--;
                else if (nums[left] + nums[right] + nums[i] < 0) left++;
                else {
                    res.push_back({nums[left], nums[right], nums[i]});
                    // 跳过左指针重复值
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    // 跳过右指针重复值
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    // 双指针收缩，继续找下一组
                    left++, right--;
                }
            }
        }
        return res;
    }
};

有效三角形的个数

本题算是三数之和的变式，只不过要求三数组成三角形而不是和为零。三角形性质：任意两边之和大于第三边。

1. 先排序，依旧固定一边（最长边）。
2. 利用三角形两小边之和大于第三边性质寻找三个符合要求的边，符合要求则计入次数。

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int sum = 0;
        for (int i = n - 1; i > 1; i--) {
            int left = 0, right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    sum += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return sum;
    }
};

四数之和

注意样例里面存在超大数，所以需要注意 int 无法承载的问题，需使用 long long 进行中间计算。

原理与三数之和类似，增加一层循环即可。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        for (int j = n - 1; j >= 3; j--) {
            if (j < n - 1 && nums[j] == nums[j + 1]) continue;
            int t = target - nums[j];
            for (int i = j - 1; i >= 2; i--) {
                if (i < j - 1 && nums[i] == nums[i + 1]) continue;
                int left = 0, right = i - 1;
                while (left < right) {
                    long long sum = (long long)nums[left] + nums[right] + nums[i];
                    if (sum < t) left++;
                    else if (sum > t) right--;
                    else {
                        res.push_back({nums[left], nums[right], nums[i], nums[j]});
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++, right--;
                    }
                }
            }
        }
        return res;
    }
};

快慢双指针解决环形问题

用跑圈的问题来类比，如果一个快的人和慢的人在环形跑道跑步，如果他们一直是恒速前进，那么必定相遇。快慢双指针也类似这个问题。

环形链表

程序员遇到的经典环形问题是判断链表是否有环。

采用快慢指针的思想，如果有环就必定能相遇，而如果没环必定能越界。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
            if (slow == fast) return true;
        }
        return false;
    }
};

快乐数

本题的两种情况其实可以看作是一种情况：有环（环内无 1）或有环（环内只有 1，即为快乐数）。所以只需要判断快慢指针相遇的时候他们所指元素的值是不是 1，即可判断是否是快乐数。

class Solution {
public:
    int get_sosq(int& n) {
        int sum = 0;
        while (n) {
            sum += pow((n % 10), 2);
            n /= 10;
        }
        return sum;
    }

    bool isHappy(int n) {
        int show = n, fast = n;
        show = get_sosq(show);
        fast = get_sosq(fast);
        fast = get_sosq(fast);
        while (show != fast) {
            show = get_sosq(show);
            fast = get_sosq(fast);
            fast = get_sosq(fast);
        }
        if (fast == 1) return true;
        return false;
    }
};