双指针是一种非常实用的技巧，往下又可细分为快慢指针、左右指针和滑动窗口等

快慢指针

快慢指针一般用于解决链表问题，如141. 环形链表

快指针一次走两步，慢指针一次走一步，如果没有环，快指针则会多绕一圈后与慢指针相遇

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head:
            return False
        slow,quick=head,head
        while(slow and slow.next and quick and quick.next and quick.next.next):
            slow=slow.next
            quick=quick.next.next
            if slow==quick:
                return True
        return False

再如142. 环形链表 II

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        flag=False
        fast=slow=head
        while(fast and fast.next):
            fast=fast.next.next
            slow=slow.next
            if fast==slow:
                flag=True
                break
        if not flag:return None
        slow=head
        while(slow!=fast):
            fast=fast.next
            slow=slow.next
        return slow

其中逻辑如下：

a->(b,c)
a+b+c=2(a+b)
c=a+b
从头开始走a+b或c时相遇

以及876. 链表的中间结点

快指针的速度是慢指针的两倍，快指针走到尾时，慢指针刚好处于中间结点

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        quick,slow=head,head
        while quick and quick.next:
            slow=slow.next
            quick=quick.next.next
        return slow

只要掌握了快慢指针，很快就能解决这类链表问题了

左右指针

左右指针用在同一个数组里，可以进行二分查找，关于二分的细节，可以看我的另一篇文章算法之二分查找
左右指针用在两个数组里，可以计算两个数组的交集,以及合并两个有序数组

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        l,r=0,0
        res=[]
        while(l<len(nums1) and r<len(nums2)):
            if(nums1[l]==nums2[r]):
                res.append(nums1[l])
                l+=1
                r+=1
            elif(nums1[l]<nums2[r]):
                l+=1
            elif(nums1[l]>nums2[r]):
                r+=1
        return list(set(res))

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        res = []
        l, r = 0, 0
        while l < m or r < n:
            if l == m:
                res.append(nums2[r])
                r += 1
            elif r == n:
                res.append(nums1[l])
                l += 1
            elif nums1[l] < nums2[r]:
                res.append(nums1[l])
                l += 1
            else:
                res.append(nums2[r])
                r += 1
        nums1[:] = res	# modify nums1 in-place

滑动窗口

滑动窗口顾名思义，就是一个在不断滑动(一般是向右滑动)的窗口，窗口扩张右界时增大，收缩左界时减小，窗口在滑动过程中不会往左倒退(也就是说，左右边界的下标一直在增大，不会减小)

滑动窗口的核心在于

扩张右界（一般是为了找到可行解）
收缩左界（一般是为了去除部分解，找到局部最优可行解）

周赛刚好遇到一题：考试的最大困扰度

class Solution:
    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
        n=len(answerKey)
        nums=[1 if x=='T' else 0 for x in answerKey]
        

        res1 = 0
        l, r = 0, 0
        z = 0 
        while r < n:
            if nums[r] == 0:
                z += 1
            while z > k:
                if nums[l] == 0:
                    z -= 1
                l += 1
            res1 = max(res1, r - l + 1)
            r += 1
        
        res2 = 0
        l, r = 0, 0
        z = 0 
        while r < n:
            if nums[r] == 1:
                z += 1
            while z > k:
                if nums[l] == 1:
                    z -= 1
                l += 1
            res2 = max(res2, r - l + 1)
            r += 1
        return max(res1,res2)