稀有猿诉

十年磨一剑,历炼出锋芒,说话千百句,不如码二行。

双指针总结

双指针是指用两个引用或者索引,或者某种键为主的操作手段,在很多场景有重要的应用,比如链表。有些时候还能成为比较巧妙的解题手段。今天就来总结一下双指针的使用。

双指针的套路

根据不同的场合和用法,双指针可以分为同向双指针对撞指针

同向双指针

又可以细分为滑动窗口,以及快慢指针。

滑动窗口

两个指针,通常一个慢一个快,之间的子数组具有某种特质,快指针(也称右指针)正常向前遍历,新元素会加入,同时左指针也会向前移动,就像一个向前开动的公交车一样。

有些窗口大小是固定的,有些则是不固定的,看具体情况而定,新元素进入以及窗口中的元素移出窗口也要视题目中的具体条件而定。

快慢指针

最为经典的场景就是解决一坨单链表问题,比如找链表的中间节点,或者找环,以及归并等等。

此外,快慢指针也常用于数组,通常是涉及数组的元素移动,此类型的要点就是一个指针正常遍历原数组,此为快指针,一个指针用指向结果数组,快指针正常遍历,慢指针依据某些条件才向后移动。

对撞指针

就是一个从前往后遍历,一个从后往前遍历,循环中止条件是两指针相遇,通常用在二分查找,回文相关,反转数组列表,或者其他场合。

双指针技巧

双指针,除了以上几种比较典型之外啊,其实也挺宽泛的,只要用了两个以上的指针(下标)就算得上是双指针,也没啥固定的模式。

但有时,有两个常见的技巧能大幅优化效率和代码,一个就是逆向思维,比如一些涉及归并的题目中,如果用常规思路,从前往后,可能用额外空间才可以,但如果从后往前,或者从两头往中间,可能就打开了一片新天地。这里的正向和逆向视具体情况而定,比如有些归并类的是直觉上是从前往后,那这就是正向,从后往前则是逆向;再如一些中间分段的数组如山峰或者山谷形的,从间往往两头是正向,那从两头往中间则逆向。如题977。

还有一个技巧是,如果要求返回数组的顺序由原数组决定,但数据 的选择由计算规则确定,也就是说我们是在计算后的数组上应用双指针进行选择,但又要返回原数据中的数据顺序,这时呢,其实可以不必直接用双指针在计算后的数组中选择结果,可以先行移动指针到目标范围,然后再遍历去选择结果。典型的问题是题658。

典型问题

题目 题解 要点说明
167. 两数之和 II - 输入有序数组 题解 经典对撞指针
658. 找到 K 个最接近的元素 题解 先移指针到目标范围,再选择结果
977. 有序数组的平方 题解 逆向思维
11. 盛最多水的容器 题解 对撞指针
557. 反转字符串中的单词 III 题解
189. 轮转数组 题解
876. 链表的中间结点 题解 经典快慢指针
19. 删除链表的倒数第 N 个结点 题解 经典快慢指针
567. 字符串的排列 题解 经典滑动窗口
3. 无重复字符的最长子串 题解 滑动窗口
题解
题解

参考资料

Comments