双指针

双指针（Two Pointers）是一种常用的算法技巧，主要用于处理数组或链表等线性结构的问题。其核心思想是使用两个指针（或索引）来遍历数据结构，通过指针的移动来解决问题。

双指针的常见应用场景

1. 有序数组的两数之和：在有序数组中查找两个数，使它们的和等于目标值。
2. 移除元素：在数组中移除特定值的元素，同时保持原数组顺序。
3. 反转数组或字符串：通过双指针从两端向中间遍历，实现反转。
4. 链表中的环检测：使用快慢指针判断链表中是否存在环。
5. 滑动窗口：通过双指针维护一个窗口，解决子数组或子字符串问题。

双指针的分类

1. 同向双指针：两个指针从同一侧开始移动，通常用于滑动窗口或移除元素。
2. 对向双指针：两个指针分别从两端向中间移动，适用于有序数组的两数之和或反转问题。
3. 快慢指针：两个指针以不同速度移动，常用于链表中的环检测或找中点。

示例

1. 有序数组的两数之和

给定一个有序数组 nums 和目标值 target，找到两个数使它们的和等于 target。

def two_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []

2. 移除元素

给定一个数组 nums 和一个值 val，移除所有等于 val 的元素，并返回新数组的长度。

def remove_element(nums, val):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow += 1
    return slow

总结

双指针通过巧妙地移动两个指针来高效解决问题，通常能将时间复杂度从 (O(n^2)) 降低到 (O(n))，是一种非常实用的算法技巧。

---

好的！以下是使用 C++ 实现双指针的示例代码，涵盖两个经典问题：有序数组的两数之和 和 移除元素。

---

1. 有序数组的两数之和

给定一个有序数组 nums 和目标值 target，找到两个数使它们的和等于 target，并返回它们的下标。

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

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 {}; // 如果没有找到，返回空数组
}

int main() {
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    vector<int> result = twoSum(nums, target);
    if (!result.empty()) {
        cout << "Indices: " << result[0] << ", " << result[1] << endl;
    } else {
        cout << "No solution found!" << endl;
    }
    return 0;
}

输出：

Indices: 0, 1

---

2. 移除元素

给定一个数组 nums 和一个值 val，移除所有等于 val 的元素，并返回新数组的长度。

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

int removeElement(vector<int>& nums, int val) {
    int slow = 0; // 慢指针
    for (int fast = 0; fast < nums.size(); fast++) { // 快指针
        if (nums[fast] != val) {
            nums[slow] = nums[fast]; // 将不等于 val 的元素移到前面
            slow++;
        }
    }
    return slow; // 返回新数组的长度
}

int main() {
    vector<int> nums = {3, 2, 2, 3};
    int val = 3;
    int length = removeElement(nums, val);
    cout << "New length: " << length << endl;
    cout << "Modified array: ";
    for (int i = 0; i < length; i++) {
        cout << nums[i] << " ";
    }
    cout << endl;
    return 0;
}

输出：

New length: 2
Modified array: 2 2

---

3. 快慢指针：链表的环检测

以下是一个使用快慢指针检测链表中是否存在环的示例。

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

bool hasCycle(ListNode* head) {
    if (!head || !head->next) return false; // 空链表或只有一个节点
    ListNode* slow = head; // 慢指针
    ListNode* fast = head; // 快指针
    while (fast && fast->next) {
        slow = slow->next; // 慢指针走一步
        fast = fast->next->next; // 快指针走两步
        if (slow == fast) {
            return true; // 快慢指针相遇，说明有环
        }
    }
    return false; // 无环
}

int main() {
    // 创建一个带环的链表
    ListNode* head = new ListNode(3);
    head->next = new ListNode(2);
    head->next->next = new ListNode(0);
    head->next->next->next = new ListNode(-4);
    head->next->next->next->next = head->next; // 形成环

    if (hasCycle(head)) {
        cout << "Cycle detected!" << endl;
    } else {
        cout << "No cycle found." << endl;
    }
    return 0;
}

输出：

Cycle detected!

---

总结

以上是 C++ 中双指针的三种经典应用：

1. 对向双指针：用于有序数组的两数之和。
2. 同向双指针：用于移除元素。
3. 快慢指针：用于链表的环检测。

双指针技巧能够显著提高算法的效率，通常将时间复杂度从 (O(n^2)) 降低到 (O(n))，是解决线性结构问题的利器！