最后更新于
最后更新于
双指针可以应用在不同的场景, 虽然都是用两个指针, 但用法, 即指针的移动方法大相径庭, 在移动方向, 移动逻辑, 移动速度上都可能有区别. 下面是刷题过程中遇到的经典双指针案例.
滑动窗口可以等价为双指针的一种, 用前后两个指针控制窗口的范围.
例如在中, 使用双指针, 保持窗口内没有重复的字符.
再例如中, 双指针控制窗口内子数组的数字之和在一定的范围内.
一般在链表中使用. 由于链表无法直接获取长度, 也无法像数组一样直接获取指定位置的元素, 因此如果我们要获取固定分位数位置的数值, 常常使用一快一慢两个指针. 例如为了获取链表中间位置的指针, 分别定义为slow_ptr和fast_ptr, slow_ptr每次移动一个结点, fast_ptr每次移动两个结点, 这样当fast_ptr移动到链表的截尾时, slow_ptr正好访问到中间节点, 无论链表的长度奇偶.
例如在中就有使用上述的快慢指针.