双指针算法是一种常用的优化数组或链表操作的技巧，它可以避免使用暴力搜索或者多重循环，从而提高算法的效率。双指针算法的基本思想是使用两个指针（变量）来指向数组或链表中的元素，根据问题的要求，移动这两个指针来寻找目标值或者判断条件。在 C++ 中，可以使用指针类型的变量或者迭代器来实现双指针算法。

双指针算法有两种常见的形式：快慢指针和对撞指针。快慢指针是指两个指针以不同的速度或者步长在数组或链表中移动，常用于解决链表中的环问题、寻找中间节点等。对撞指针是指两个指针分别指向数组或链表的首尾，然后同时向中间移动，常用于解决两数之和、判断回文串等问题。

举个例子

下面是一个用 C++ 实现的双指针算法的例子，它的目的是在一个有序数组中找出两个数，使得它们的和等于给定的目标值。这个问题可以用对撞指针来解决，具体的思路是：

• 定义两个指针 left 和 right，分别指向数组的第一个元素和最后一个元素。
• 计算 left 和 right 所指向的元素的和 sum，并与目标值 target 比较。
• 如果 sum 等于 target，说明找到了一对解，输出 left 和 right 的下标，并结束循环。
• 如果 sum 小于 target，说明和不够大，需要增大 sum，因此将 left 向右移动一位，使得 left 所指向的元素变大。
• 如果 sum 大于 target，说明和太大，需要减小 sum，因此将 right 向左移动一位，使得 right 所指向的元素变小。
• 重复上述步骤，直到 left 和 right 相遇或者找到解为止。

代码如下：

#include <iostream>
#include <vector>
using namespace std;

// 函数功能：在有序数组 nums 中找出两个数，使得它们的和等于 target
// 参数：nums 是一个有序数组，target 是目标值
// 返回值：一个包含两个下标的数组，如果没有找到解，返回空数组
vector<int> twoSum(vector<int>& nums, int target) {
    // 定义两个指针，分别指向数组的首尾
    int left = 0, right = nums.size() - 1;
    // 定义一个存放结果的数组
    vector<int> res;
    // 循环条件是 left < right
    while (left < right) {
        // 计算两个指针所指向的元素的和
        int sum = nums[left] + nums[right];
        // 如果和等于目标值，将两个下标放入结果数组，并结束循环
        if (sum == target) {
            res.push_back(left);
            res.push_back(right);
            break;
        }
        // 如果和小于目标值，将左指针向右移动一位
        else if (sum < target) {
            left++;
        }
        // 如果和大于目标值，将右指针向左移动一位
        else {
            right--;
        }
    }
    // 返回结果数组
    return res;
}

int main() {
    // 定义一个有序数组
    vector<int> nums = {2, 7, 11, 15};
    // 定义一个目标值
    int target = 9;
    // 调用函数，得到结果
    vector<int> res = twoSum(nums, target);
    // 如果结果不为空，输出结果
    if (!res.empty()) {
        cout << "找到了一对解，下标分别是：" << res[0] << " 和 " << res[1] << endl;
    }
    // 如果结果为空，输出提示信息
    else {
        cout << "没有找到解" << endl;
    }
    return 0;
}

Q & F

这是否严谨？sum 小于 target，说明和不够大，可将 left 向右移动一位，为什么不能将right右移一位？

如果 right 右移一位，那么 sum 一定会变大，但是可能会超过 target，导致结果不正确。所以，只有将 left 右移一位才能保证 sum 不会超过 target，而且有可能等于 target。这是双指针算法的一个重要的原则。

更多例子

下面用C++代码给出一些双指针算法的例子：

• 快慢指针判断链表是否有环：

// 定义链表节点结构体
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 判断链表是否有环的函数
bool hasCycle(ListNode *head) {
    // 如果链表为空或只有一个节点，返回false
    if (head == NULL || head->next == NULL) return false;
    // 定义快慢指针，初始都指向头节点
    ListNode *slow = head, *fast = head;
    // 循环条件是快指针不为空且快指针的下一个节点不为空
    while (fast != NULL && fast->next != NULL) {
        // 快指针每次移动两个位置，慢指针每次移动一个位置
        fast = fast->next->next;
        slow = slow->next;
        // 如果快慢指针相遇，说明有环，返回true
        if (fast == slow) return true;
    }
    // 如果循环结束，快慢指针没有相遇，说明没有环，返回false
    return false;
}

• 左右指针判断字符串是否回文：

// 判断字符串是否回文的函数
bool isPalindrome(string s) {
    // 如果字符串为空，返回true
    if (s.empty()) return true;
    // 定义左右指针，初始分别指向字符串的开头和末尾
    int left = 0, right = s.size() - 1;
    // 循环条件是左指针小于右指针
    while (left < right) {
        // 如果左指针指向的字符不是字母或数字，左指针右移
        if (!isalnum(s[left])) left++;
        // 如果右指针指向的字符不是字母或数字，右指针左移
        else if (!isalnum(s[right])) right--;
        // 否则，比较左右指针指向的字符是否相等，忽略大小写
        else {
            // 如果不相等，返回false
            if (tolower(s[left]) != tolower(s[right])) return false;
            // 如果相等，左指针右移，右指针左移
            else {
                left++;
                right--;
            }
        }
    }
    // 如果循环结束，左右指针没有发现不相等的字符，返回true
    return true;
}

• 对撞指针寻找三个数之和：

// 寻找三个数之和的函数
vector<vector<int>> threeSum(vector<int>& nums) {
    // 定义结果数组
    vector<vector<int>> res;
    // 如果数组为空或长度小于3，返回空数组
    if (nums.empty() || nums.size() < 3) return res;
    // 对数组进行升序排序
    sort(nums.begin(), nums.end());
    // 遍历数组，固定第一个数
    for (int i = 0; i < nums.size() - 2; i++) {
        // 如果第一个数大于0，后面的数都大于0，不可能和为0，直接返回结果
        if (nums[i] > 0) return res;
        // 如果第一个数和前一个数相同，跳过重复的情况
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        // 定义左右指针，初始分别指向第一个数的后一个数和数组的最后一个数
        int left = i + 1, right = nums.size() - 1;
        // 循环条件是左指针小于右指针
        while (left < right) {
            // 计算三个数之和
            int sum = nums[i] + nums[left] + nums[right];
            // 如果和为0，说明找到了一组解，将其加入结果数组
            if (sum == 0) {
                res.push_back({nums[i], nums[left], nums[right]});
                // 左指针右移，跳过重复的数
                while (left < right && nums[left] == nums[left + 1]) left++;
                // 右指针左移，跳过重复的数
                while (left < right && nums[right] == nums[right - 1]) right--;
                // 左右指针同时向中间移动
                left++;
                right--;
            }
            // 如果和小于0，说明需要增大和，左指针右移
            else if (sum < 0) left++;
            // 如果和大于0，说明需要减小和，右指针左移
            else right--;
        }
    }
    // 返回结果数组
    return res;
}