双指针_专项题单练习

双指针

双指针本质是对当前位置或当前范围的一种表示，通过两个变量表示下标来模拟对位置的指向，通过移动这两个变量来控制位置或范围的变化。它的核心思想在于让两个指针在序列上以特定规律移动，从而将原本需要多重循环的暴力解法优化为更高效率的算法。

双指针的最大优势在于其卓越的性能。它通过单次线性遍历和巧妙的指针移动，避免了不必要的嵌套循环，成功将许多问题的时间复杂度从 O(n²) 优化至 O(n)。这种技巧不仅提升了效率，更让代码逻辑变得清晰直观。

双指针主要模拟了考虑和选择的过程，往往与枚举、贪心的思想结合使用，使用前有时需要先进行排序。

1. 同数组指针

1.1 同向双指针

同数组中，两个指针分别指向两个位置，并且两个指针移动方向都相同（一般是都从前向后），此时这两个位置作为边界形成的范围就是当前选择的范围。

这个范围的长度如果是固定的，就视为一个滑动窗口，往往用于解决连续子数组问题，还可以结合前缀和减少重复计算，结合单调队列快速获得区间极值。

如果问题是找出数组中符合要求的最长连续长度，此时双指针表示范围的长度是不固定的，就需要根据情况调整左右指针移动来实现范围长度的变化。这就是尺取，结合贪心的思想，考虑对前面位置的放弃和后续位置的选取，来调整指针的移动。

当我们进行数组内的范围选择时，就可以采用同向双指针的方法描述当前范围，复杂度会低于嵌套循环。同向双指针的情况下，指针模拟了选择范围的边界，当我们需要改变边界位置来改变选择范围时，就通过移动指针指向位置来模拟边界的变化，从而实现范围的改变。此类问题中需要关注指针的移动策略以及所需内容的记录，以便后续的计算。