[数据结构与算法]算法学习笔记——常用技巧：双指针（快慢指针和左右指针）

双指针技巧TwoPointers

数组、链表、子串相关的题目，常考虑使用双指针技巧

• 快慢指针用于链表判断成环、在链表归并排序时找中点
• 左右指针用于数组字符串问题，一般是左右两端相向而行，如二分搜索、反转数组、两数之和问题
• 更深入的是滑动窗口算法，严格来说它属于快慢指针在数组字符串上的应用，用于解决字符串匹配问题

快慢指针

快慢指针一般都初始化指向链表头节点head，前进时快指针fast在前，慢指针slow在后

1. 判断链表中是否有环

单靠一个指针，在有环的链表中会陷入死循环，因为没有None作为尾部结点
要判断是否有环，让快指针fast每次前进2步，慢指针slow每次前进1次，如果有环，最终快指针会超过慢指针一圈，两者相遇说明有环

##class LinkedList(object):
##    """单链表"""
##
##    def __init__(self):
##        self._head = None


class ListNode(object):
    """单链表的结点"""

    def __init__(self, data):
        self.data = data
        self.next = None


def hasCycle(head: ListNode):
    fast = slow = head
    while fast != None and fast.next != None:
        fast = fast.next.next
        slow = slow.next
        if fast == slow:
            return True
    return False


a, b, c, d = ListNode('a'), ListNode('b'), ListNode('c'), ListNode('d')
a.next = b
b.next = c
c.next = d
d.next = None
print(hasCycle(a))

2. 已知链表中有环，返回这个环的起始位置

fast和slow相遇后，设置其中任何一个指针指向head，然后两者同速度前进，再次相遇时所在结点就是环的起始结点
原理：

• 快慢指针相遇时，假设slow走了k步，则fast走了2k步，环的长度必为k
• 假设slow已经从环的起点走了m步，再走(k-m)步到达环的起点
• 巧的是，从head前进(k-m)步，也到达环的起点，因为当前slow走了k步且超过了环的起点m步

def findStartOfCycle(head: ListNode):
    """已知链表中有环，返回这个环的起始位置"""
    fast = slow = head
    while fast != None and fast.next != None:
        fast = fast.next.next
        slow = slow.next
        if fast == slow:
            break

    # fast和slow相遇后，设置其中任何一个指针指向head，然后两者同速度前进，再次相遇时所在结点就是环的起始结点
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    return slow

3. 寻找无环单链表的中点

寻找无环单链表的中点，常常用于对链表进行归并排序
让快指针fast每次前进2步，慢指针slow每次前进1次，最终当快指针到达链表尽头，慢指针就停在链表中点位置(若链表长度为偶数，慢指针停在中间偏右的位置)

def getMiddle(head: ListNode):
    """寻找无环单链表的中点"""
    fast = slow = head
    while fast != None and fast.next != None:
        fast = fast.next.next
        slow = slow.next
    return slow

4. 寻找无环单链表的倒数第k个元素

让快指针fast先走k步，然后快、慢指针同速前进，最终当快指针到达链表尽头，慢指针就停在链表倒数第k个元素

def getKFromLast(head: ListNode, k: int):
    """寻找无环单链表的倒数第k个元素,k需要小于链表长度"""
    fast = slow = head
    for _ in range(k):
        fast = fast.next
    while fast != None:
        slow = slow.next
        fast = fast.next
    return slow

左右指针

只要数组有序，就应该想到双指针技巧
快慢指针一般运用在数组中，初始化左指针left=0，右指针right=len(list)-1

1. 两数之和

在升序的有序数组中找两个数，使得两数之和为target，返回两数下标

def twoSum(arr: list, target: int) -> list:
    """升序的有序数组中找两个数，使得两数之和为target，返回两数下标"""
    left = 0
    right = len(arr) - 1
    while (left < right):
        if arr[left] + arr[right] == target:
            return [left, right]
        elif arr[left] + arr[right] < target:
            left += 1  # 让sum大一点
        elif arr[left] + arr[right] > target:
            right -= 1  # 让sum小一点
    return []


arr = [1, 3, 4, 5, 7, 10]
print(twoSum(arr, 14))

2. 二分搜索

在有序数组中查找某个值，详见算法学习笔记——常用技巧：双指针（二分搜索）

3. 反转数组

反转数组的底层实现，也是用两端的左右指针向中间收缩，并交换元素

4. 滑动窗口算法

详见算法学习笔记——常用技巧：双指针（滑动窗口算法）