白云移动网站建设,上海装修公司排名榜,wordpress+音乐盒,wordpress小程序不能评论双指针法#xff08;Two Pointers#xff09;是一种常用的算法技巧#xff0c;通常用于解决数组或链表中的问题。这种技巧通过维护两个指针#xff0c;通常分别指向数组或链表的不同位置#xff0c;来协同解决问题。双指针法一般有两种类型#xff1a;快慢指针和左右指针…双指针法Two Pointers是一种常用的算法技巧通常用于解决数组或链表中的问题。这种技巧通过维护两个指针通常分别指向数组或链表的不同位置来协同解决问题。双指针法一般有两种类型快慢指针和左右指针。
快慢指针Slow-Fast Pointers 概念快慢指针是指两个指针一个快指针和一个慢指针它们以不同的速度移动来解决问题。慢指针一般每次移动一个位置而快指针一般每次移动两个或多个位置。 应用场景常用于判断链表是否有环快慢指针在环形链表中一定会相遇、链表中点、链表倒数第K个节点等问题。
左右指针Two Pointers 概念左右指针是指两个指针一个指向开始位置左指针一个指向结束位置右指针它们向中间移动解决问题。 应用场景常用于有序数组或链表中的查找、求和、两数之和等问题。左右指针可以根据问题的特点进行不同的移动策略比如向内移动、向外移动或向中间移动。
双指针算法的优势 时间复杂度双指针算法通常时间复杂度较低因为每个指针只遍历一次数组或链表。 空间复杂度双指针算法通常不需要额外的空间只需要常数级的额外空间。 可解决问题双指针算法可以解决许多数组和链表相关的问题包括查找、求和、判断等。
示例 快慢指针判断链表是否有环。 左右指针在有序数组中找到两个数使它们的和等于目标值。 P1. 洛谷p1102A-B数对
分析双指针优化算法常常是让找东西更方便而查找有序区间是最优的最坏也是o(n)级别的时间复杂度。而原数组排序后所要找的A存在的区间和B存在的区间宏观大小上就相差一个C。而查找这样的区间使用双指针必然可以得到优化。
#includeiostream
#includealgorithm
using namespace std;int main()
{int n,c;cinnc;int* numsnew int[n];for(int i0;in;i){cinnums[i];}long long result0;sort(nums,numsn);int left0;int right0;//for(int i0;in;i) coutnums[i] ;for(int dexa0;dexan;dexa){while(rightnnums[right]-nums[dexa]c) right;while(leftnnums[left]-nums[dexa]c) left;if(nums[dexa]-nums[left]-cnums[dexa]-nums[right-1]-cright-10)result(right-left);}coutresult;return 0;
}
