双指针的详细教程

双指针算法是一种常用的算法技巧，它通常用于在数组或字符串中进行快速查找、匹配、排序或移动操作。

双指针并非真的用指针实现，一般用两个变量来表示下标（在后面都用指针来表示）

双指针算法使用两个指针在数据结构上进行迭代，并根据问题的要求移动这些指针。

双指针往往也和单调性、排序联系在一起，在数组的区间问题上，暴力法的时间复杂度往往都是O(n^2)的，但双指针利用“单调性”可以优化到O（n）

常见的双指针模型有

（1）对撞指针

指的是两个指针left、right分别指向序列的第一个元素和最后一个元素

然后I指针不断递增，r不断递减，直到两个指针的值相撞后错开（即l>=r），或者满足其他的特殊条件为止

对撞指针一般是用来解决有序数组或者字符串问题（区间问题）

查找有序数组中满足某些约束条件的一组元素问题：比如二分查找、数字之和等问题。

字符串反转问题：反转字符串，回文数等问题。

1 使用两个指针left,right.left指向序列第一个元素，即：left=1，right指向序列最后一个元素，即：right：n。

2 在循环体中将左右指针相向移动，当满足一定条件时，将左指针右移，left++.当满足另外一定条件时，右指针左移right--

直到两指针相撞（即left==right）,或者满足其他要求的特殊条件时，跳出循环体

例题实战

题目描述

给定一个长度为n的字符串S，请你判断字符串S是否时回文

输入描述

输入仅一行包含一个字符串S

1<=|S|<=10^6,保证S只包含大小写字母

输出描述

若字符串S为会问串，则输出Y，否则输出N

输入输出样例

示例 1

abcba

输出Y

回文判定

对撞指针，每次判断s[l]和s[r]是否相等。如果相等，进一步移动，否则直接判断“不是回文串”

（2）快慢指针

快慢指针一般比对撞指针更难想，更难写。

指的是两个指针，从同一侧开始遍历序列，且移动的步长一个块，一个慢

移动快的指针被称为快指针，一动漫的指针被称为慢指针

为了方便理解，我们称快指针为r,慢指针为l,这样慢指针和快指针构成的区间为[l,r]

两个指针以不同的速度，不同策略移动，直到快指针移动到数组尾端，或者两指针相交，或者满足其他特殊条件为止。

1.使用两个指针l,r.一般l指向序列的第一个元素，即：l=1,r一般指向序列第零个元素，即：r=0。即初始时区间[l,r]=[1,0]表示为空区间。

2.在循环体中将左右指针向右移动。当满足一定条件时，将慢指针右移，即l++。当满足另外一定条件时（也可能不需要满足条件），将快指针右移，即r++，保持[l,r]为合法区间

3.到指针移动到数组尾端（即l==n且r==n），或者两指针相交，或者满足其他特殊条件时，跳出循环 

例题

给定一个长度为n的序列a1,a2,...an和一个常数S

对于一个连续区间如果它的区间和大于或等于S，则称它为美丽区间

对于一个美丽区间，如果区间长度越短，它越美丽

请你从序列中找出最美丽的区间

输入描述

第一含包含两个整数n,S,其含义如题所述

接下来一行包含n个整数，分别表示a1,a2,...an

输出描述

输出共遗憾，包含一个整数，表示最美丽的区间长度

若不存在任何美丽区间，则输出0