双指针算法精解：对撞指针与快慢指针的妙用与实践

目录

一、对撞指针（Colliding Pointers）

1.细节

2.思想

3.功能

4.代码示例

二、左右指针（快慢指针，Slow-Fast Pointers）

1.细节

2.思想

3.功能

4.代码示例

三、总结

一、对撞指针（Colliding Pointers）

1.细节

• 定义：对撞指针使用两个指针，一个从数组的起始位置（左指针）开始，另一个从数组的末尾（右指针）开始，两个指针向中间移动，直到相遇或交叉。

• 适用场景：通常用于有序数组或可以通过排序转化为有序数组的问题。

• 时间复杂度：O(n)，因为每个指针最多遍历数组一次。

2.思想

• 核心思想：通过左右指针的协同移动，缩小问题的搜索范围。利用数组的有序性，通过比较指针指向的值与目标值的关系，决定移动哪个指针。

• 优势：避免了暴力搜索的高时间复杂度（O(n^2)），将问题优化为线性时间复杂度。

3.功能

• 典型应用：

  1. 两数之和：在有序数组中找到两个数，使它们的和等于目标值。

  2. 三数之和：找到数组中三个数，使它们的和等于目标值。

  3. 回文串判断：判断一个字符串是否为回文串。

4.代码示例

#include <vector>
#include <algorithm>

// 两数之和问题
std::vector<int> twoSum(std::vector<int>& nums, int target) 
{
    std::sort(nums.begin(), nums.end()); // 首先对数组排序
    int left = 0;
    int right = nums.size() - 1;
    while (left < right) 
    {
        int sum = nums[left] + nums[right];
        if (sum == target) 
        {
            return {nums[left], nums[right]}; // 返回找到的两个数
        } 
        else if (sum < target) 
        {
            left++; // 和小于目标值，左指针右移
        } 
        else 
        {
            right--; // 和大于目标值，右指针左移
        }
    }
    return {}; // 如果没有找到，返回空数组
}

二、左右指针（快慢指针，Slow-Fast Pointers）

1.细节

• 定义：快慢指针使用两个指针，一个移动速度快（快指针），另一个移动速度慢（慢指针）。通常快指针每次移动两步，慢指针每次移动一步。

• 适用场景：常用于链表或数组中的循环检测、中点查找、滑动窗口等问题。

• 时间复杂度：O(n)，因为每个指针最多遍历链表或数组一次。

2.思想

• 核心思想：通过快慢指针的速度差，解决一些需要定位特定位置或检测特定模式的问题。例如，快指针的速度是慢指针的两倍，可以用来找到链表的中点或检测环。

• 优势：避免了额外的空间开销（如使用哈希表），同时保持线性时间复杂度。

3.功能

• 典型应用：

  1. 链表环检测：判断链表中是否存在环。

  2. 链表中点查找：找到链表的中点。

  3. 滑动窗口：解决子数组或子字符串的相关问题。

4.代码示例

#include <iostream>

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

// 链表环检测
bool hasCycle(ListNode* head) 
{
    if (head == nullptr || head->next == nullptr) 
    {
        return false;
    }
    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; // 无环
}

// 链表中点查找
ListNode* findMiddle(ListNode* head) 
{
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast != nullptr && fast->next != nullptr) 
    {
        slow = slow->next; // 慢指针每次移动一步
        fast = fast->next->next; // 快指针每次移动两步
    }
    return slow; // 慢指针指向中点
}

三、总结

        双指针技术是一种非常实用的算法设计思想，能够有效解决许多经典问题。掌握对撞指针和左右指针的使用场景和实现细节，可以显著提升算法能力。