C++——双指针_c++双指针

双指针是指在算法或数据结构中使用两个指针来解决问题的技巧。这两个指针通常分别指向数组、链表或字符串等数据结构中的元素或位置。

常见的双指针技巧包括：

1、快慢指针：使用两个指针以不同的速度遍历数组或链表，常用于解决问题如判断链表是否有环、寻找链表的中间节点等。

2、左右指针：在有序数组或字符串中，将一个指针指向开头，另一个指针指向末尾，通过根据问题的要求移动指针来搜索目标值、判断是否满足某个条件等。

3、对撞指针：在有序数组或字符串中，将两个指针分别指向开头和末尾，并同时向中间移动，常用于寻找两个数之和、判断是否回文串等问题。

4、快慢指针替换：在某些情况下，可以使用快慢指针来替换传统的单指针遍历，以提高算法的效率。

两数之和：给定一个有序数组和一个目标值，找出数组中和为目标值的两个数的索引。

vector<int> twoSum(vector<int>& nums, int target) {
    int left = 0;
    int 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 {}; // 如果没有找到匹配的数对，返回空向量
}

判断链表是否有环：给定一个链表，判断链表中是否有环。

bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            return true; // 链表中存在环
        }
    }
    return false; // 链表中不存在环
}