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;
}