C++程序实现的双指针技术

双指针技术是算法中的常见技巧，常用于解决数组或链表中的问题。在 C++ 中，通过指针实现双指针技术非常简单。

双指针技术的基本原理

双指针技术基于两个指针进行操作。例如，在数组中使用双指针技术时，通常会使用两个指针 left 和 right，它们分别指向数组的最左侧和最右侧。

在算法中，使用双指针可以避免使用暴力算法，从而大大提高算法的执行效率。

用C++实现双指针技术的示例

下面是一个使用双指针技术的示例 – 在有序数组中查找目标元素的位置：

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

上面的代码使用两个指针 left 和 right，并且在每次循环时都更新指针的位置。如果中间位置的元素等于目标元素，则返回该位置；否则根据元素的大小更新指针的位置。如果循环结束还没有找到目标元素，则返回 -1。

双指针算法的分类

双指针算法通常被分类为两种：快慢指针和左右指针。

快慢指针

快慢指针是一种常见的算法技巧，通常用于解决链表中的问题。它们是两个指针，其中一个指针的移动速度比另一个指针快。通常，快指针会每次移动两个元素，而慢指针每次只移动一个元素。如果两个指针最终相遇，则说明链表中存在一个环。

下面是一个使用快慢指针的示例 – 判断链表中是否有环：

bool hasCycle(ListNode *head) {
    if (!head || !head->next) {
        return false;
    }
    ListNode *slow = head, *fast = head->next;
    while (slow != fast) {
        if (!fast || !fast->next) {
            return false;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    return true;
}

上面的代码使用两个指针 slow 和 fast，并且在每次循环时都更新指针的位置。如果两个指针最终相遇，则说明链表中存在一个环；否则，当 fast 指针到达链表的末尾时，说明该链表中不存在环。

左右指针

左右指针是双指针技术的一种。它们通常用于解决数组中的问题。左指针从数组的最左侧开始移动，而右指针从数组的最右侧开始移动。在每次循环中，根据特定的条件来更新左右指针的位置。

下面是一个使用左右指针的示例 – 在有序数组中查找两数之和为目标数字的下标：

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

上面的代码使用两个指针 left 和 right，并且在每次循环时都更新指针的位置。如果两个元素的和等于目标数字，则返回它们的下标；否则，根据元素的大小更新指针的位置。