cout << "\t"; 看看
双指针是一种解决问题的技巧或者思维方式,指在访问一个序列中的数据时使用两个指针进行扫描,两个指针可以是同向的,也可以是反向的。
我们的关注点可以是这两个指针指向的两个元素本身,也可以是两个指针中间的区域。二分法的思想基于这种左右指针的实现。
双指针是一种思想,一种技巧或一种方法,并不是什么特别具体的算法。在区间问题上,暴力的做法的复杂度往往达到O(n2)O(n^2)O(n2)复杂度,而双指针的思想挖掘区间“单调”性质将复杂度降到O(n)O(n)O(n)。
常用的双指针思想有:快慢指针、碰撞指针、滑动窗口等。
快慢指针:快慢指针按照某种规律运动。例如,设置快慢两个指针,快指针先移动距离,慢指针跟快指针同时移动,这样快慢指针之间总是保持一段相同的距离。常见的应用场景主要出现在链表中,如:链表的环的判断,求链表的中间节点等操作。
碰撞指针:在排序好的数组中,设置头指针和尾指针,按照规则,分别向中间靠拢。常见的应用场景主要出现在有序数组中:数组的和,二分查找等。这里需要强调的是:对于碰撞指针要用于已排序的区间。
滑动窗口:两个指针,一前一后组成滑动窗口,并计算滑动窗口中的元素的问题。常见问题:字符串匹配问题等,用来解决一些查找满足一定条件的连续区间求值或长度的问题。