C++ 算法学习——7.4.1 优化算法——双指针

双指针法（Two Pointers）是一种常用的算法技巧，通常用于解决数组或链表中的问题。这种技巧通过维护两个指针，通常分别指向数组或链表的不同位置，来协同解决问题。双指针法一般有两种类型：快慢指针和左右指针。

快慢指针（Slow-Fast Pointers）

• 概念：快慢指针是指两个指针，一个快指针和一个慢指针，它们以不同的速度移动来解决问题。慢指针一般每次移动一个位置，而快指针一般每次移动两个或多个位置。

• 应用场景：常用于判断链表是否有环（快慢指针在环形链表中一定会相遇）、链表中点、链表倒数第K个节点等问题。

左右指针（Two Pointers）

• 概念：左右指针是指两个指针，一个指向开始位置（左指针），一个指向结束位置（右指针），它们向中间移动解决问题。

• 应用场景：常用于有序数组或链表中的查找、求和、两数之和等问题。左右指针可以根据问题的特点进行不同的移动策略，比如向内移动、向外移动或向中间移动。

双指针算法的优势

• 时间复杂度：双指针算法通常时间复杂度较低，因为每个指针只遍历一次数组或链表。

• 空间复杂度：双指针算法通常不需要额外的空间，只需要常数级的额外空间。

• 可解决问题：双指针算法可以解决许多数组和链表相关的问题，包括查找、求和、判断等。

示例

• 快慢指针：判断链表是否有环。

• 左右指针：在有序数组中找到两个数使它们的和等于目标值。

---

P1. 洛谷p1102A-B数对

分析：双指针优化算法常常是让找东西更方便，而查找有序区间是最优的，最坏也是o(n)级别的时间复杂度。而原数组排序后，所要找的A存在的区间和B存在的区间宏观大小上就相差一个C。而查找这样的区间，使用双指针必然可以得到优化。

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

int main()
{
    int n,c;cin>>n>>c;
    int* nums=new int[n];
    for(int i=0;i<n;i++)
    {
        cin>>nums[i];
    }
    long long result=0;
    sort(nums,nums+n);
    int left=0;int right=0;
    //for(int i=0;i<n;i++) cout<<nums[i]<<" ";
    for(int dexa=0;dexa<n;dexa++)
    {
        while(right<n&&nums[right]-nums[dexa]<=c) right++;
        while(left<n&&nums[left]-nums[dexa]<c) left++;
        if(nums[dexa]-nums[left]==-c&&nums[dexa]-nums[right-1]==-c&&right-1>=0)
        result+=(right-left);
    }
    cout<<result;
    return 0;
}

原文地址：https://blog.csdn.net/William_Edmund/article/details/142703625

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！