双指针（尺取法）

〇、返回

一、引出

双指针（Two Pointers）是一种在数组或链表等线性数据结构中常用的算法技巧。它通过使用两个指针来遍历数据，从而有效地解决问题，通常可以将时间复杂度从 O($n^2$) 降低到 O(n)。

二、概述

双指针算法的核心思想是通过两个指针的协同工作来遍历数据结构，这两个指针可以是同向移动、反向移动或者相向移动。这种算法常用于解决需要查找满足特定条件的元素对、子数组等问题。

三、工作原理

双指针算法的工作原理可以根据具体问题的不同而有所变化，但基本步骤如下：

1. 初始化两个指针

根据问题需求，初始化两个指针的位置。例如，在一个有序数组中查找两个数使其和为某个值时，可以一个指针指向数组的起始位置，另一个指针指向数组的末尾位置。

2. 移动指针

根据当前指针所指向元素的值来决定移动哪个指针。例如，在上述例子中，如果两个指针所指向元素的和大于目标值，则移动指向较大值的指针；如果和小于目标值，则移动指向较小值的指针。

3. 检查条件

在每次移动指针后，检查是否满足题目要求的条件。如果满足，则记录结果；如果不满足，则继续移动指针。

4. 终止条件

当指针达到某种边界条件时（如两个指针相遇或其中一个指针超出数组范围），算法终止。

四、适用情况

双指针算法适用于以下几种常见情况：

查找满足特定条件的元素对

例如，在一个有序数组中查找两个数使其和为某个值。

滑动窗口问题

例如，找到数组中的一个子数组，使其和为某个值。

链表操作

例如，删除链表中的倒数第 n 个节点，可以使用快慢指针来实现。

五、代码示例（C++）

以下是一个使用双指针算法在有序数组中查找两个数使其和为某个值的 C++ 代码示例：

#include<bits/stdc++.h>

using namespace std;

int main() {

    int n,target;

    cin>>n>>target;

    vector<int> num(n);

    for (int i=0;i<n;i++) {

        cin>>num[i];

    }

    int left=0,right=n-1,ans1=-1,ans2=-1;

    while (left<right) {

        int sum=nums[left]+nums[right];

        if (sum==target) {

            ans1=nums[left];

            ans2=nums[right];

        } else if (sum<target) {

            left++;

        } else {

            right--;

        }

    }

    if (ans1==-1 and ans2==-1) {

        cout<<"答案不存在\n";

    } else {

        cout<<ans1<<" "<<ans2<<"\n";

    }

    return 0;

}

六、时间复杂度

双指针算法的时间复杂度通常为 O(n)，其中 n 是数组或链表的长度。这是因为在最坏情况下，每个元素最多被访问两次。

七、总结

双指针算法是一种高效且简洁的算法技巧，适用于多种线性数据结构上的问题。通过合理地初始化和移动两个指针，可以在一次遍历中找到满足条件的解，大大提高了算法的效率。理解双指针的基本原理和适用场景，可以帮助我们在解决相关问题时更加得心应手。