admin管理员组

文章数量:1794759

【算法/学习】双指针

引言：

双指针（Two Pointers）：指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。如果两个指针方向相反，则称为「对撞指针」。如果两个指针方向相同，则称为「快慢指针」。如果两个指针分别属于不同的数组 / 链表，则称为「分离双指针」。

在数组的区间问题上，暴力算法的时间复杂度往往是O(n^2)。而双指针利用了区间「单调性」的性质，可以将时间复杂度降到 O(n)。

指针一般情况下将分为三种类类型，分别是：

类型

特点

快慢指针

两个指针步长不同，一般情况下，快的走两步，慢的走一步

对撞指针

两个指针分别指向头尾，并往中间移动，步长不确定，一般为1

区间指针

一般为滑动窗口，两个指针及其间距视作整体，窗口有定长有变长，每次操作窗口整体向右滑动

不管是哪一种双指针，只考虑双指针部分的话 ，由于最多还是会遍历整个数组一次，因此时间复杂度取决于步长，如果步长是 1，2 这种常数的话，那么时间复杂度就是 O(N)，如果步长是和数据规模有关（比如二分法），其时间复杂度就是 O(logN)。并且由于不管规模多大，我们都只需要最多两个指针，因此空间复杂度是 O(1)。下面我们就来看看双指针的常见套路有哪些。

1. 对撞指针（相向双指针）

1.1 基本概念

对撞指针 ：指的是两个指针 left 、 right 分别指向序列第一个元素和最后一个元素，然后 left 指针不断递增， right 不断递减，直到两个指针的值相撞（即 left == right ），或者满足其他要求的特殊条件为止。 对撞指针一般用于顺序结构中，也称为左右端点指针。

求解步骤：

  • 对撞指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼近。
  • 对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：

(1) left == right（两个指针指向同一个位置） (2) left > right（两个指针错开）

1.2 伪码框架
代码语言：javascript代码运行次数：0运行复制
left, right = 0, len(nums) - 1

while left < right:
    if 满足要求的特殊条件:
        return 符合条件的值 
    elif 一定条件 1:
        left += 1
    elif 一定条件 2:
        right -= 1

return 没找到 或 找到对应值
1.3 适用范围

对撞指针一般用来解决有序数组或者字符串问题：

  • 查找有序数组中满足某些约束条件的一组元素问题：比如二分查找、数字之和等问题。
  • 字符串反转问题：反转字符串、回文数、颠倒二进制等问题。
1.4 典型例题

本文标签： 算法学习双指针

版权声明：本文标题：【算法学习】双指针 内容由林淑君副主任自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1754824689a1706931.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。