Vinn's Studio

Two-Pointer

Word count: 564Reading time: 2 min
2021/09/03 Share

双指针指在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针/左右指针）的指针进行扫描，从而达到相应的目的，常用于链表或有序数组中：双指针法充分使用了链表指向/数组有序这一特征，从而在某些情况下简化一些运算。

对撞指针

对撞指针（左右指针）是指在有序数组中，将指向最左侧的索引定义为左指针 left，指向最右侧的索引定义为右指针 right，然后从两头向中间进行数组遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def twoPointer(nums):
    left = 0
    right = len(nums) - 1
    
    while left <= right:
        if 'Some Condition':
            'Do Something'
            left += 1
        elif 'Some Condition':
            'Do Something'
            right -= 1
        else:
            'Do Something'
      
    return

快慢指针

快慢指针也是双指针，但是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针 fast 和慢指针 slow，两个指针以不同的策略移动，直到两个指针的值相等或快指针到达数组末尾（或其他特殊条件）为止，移动策略包括但不限于以下几种：

  • fast 每步移动两次，slow 每步移动一次：该策略常用于解决链表中的一些问题，例如 LeetCode 141.环形链表 中判断给定链表中是否存在环；
  • fast 先行移动一定的步数，然后 fast 与 slow 一起移动：例如 链表中倒数第 k 个节点；
  • fast 用于遍历整个有序数组，遍历过程中指向待处理序列的头部；同时 slow 用于标记已满足题目条件的序列，slow 左边的序列已经满足题目给出的要求：该策略常用于需要对有序数组本身进行 in-place 处理，使该数组满足某些条件的问题，例如 LeetCode 283. 移动零 以及 LeetCode 26. 删除有序数组中的重复项 等；

上述第三种策略的模板如下：

1
2
3
4
5
6
7
8
9
def twoPointer(nums):
    fast, slow = 0
    
    while fast < len(nums):
        if 'Some Condition':
            'Do Someting'
            slow += 1
        fast += 1
    return

Author：Lingfeng Zhu

Original Link：https://lingfengzhu.github.io/2021/09/03/Two-Pointer/

Published：September 3rd 2021, 10:41:14 am

Updated：December 28th 2021, 3:11:26 pm

Copyright：This Article Uses Attribution-NonCommercial 4.0 International as the license

CATALOG
  1. 对撞指针
  2. 快慢指针
Total : 33
2022
2021
2020
NLP Survival Analysis COVID-19 Conda Docker Python Hexo Web-Frontend Pytorch RecSys
Deep-Learning Algorithm Statistics Syntax Machine-Learning Finance