双指针技术

双指针技术 重要性：非常高

数据结构和算法的第2天

注意：每天都会有新的双指针技术问题和解决方案加入。
因此，请保持每天检查这个帖子。

让我们开始吧!
1

什么是双指针技术？

双指针是一种技术，其中使用两个指针（引用）来跟踪数组/字符串的索引。它们被精简，从而可以同时遍历数组的两个部分。

当在排序的数组中搜索配对时，这是一种有用的技术。

使用双指针技术，你可以节省空间和时间，优化你的算法。

在一个循环中，两个元素被同时访问和处理。在双指针技术中，有两种方法 -

起点和终点双指针--一个指针从起点开始，另一个指针从终点开始，直到它们相遇。

慢速和快速指针--一个慢速指针（以较慢的速度移动），另一个快速指针（移动速度是慢速指针的两倍）。

图片来源 Pluralsight

基于双指针技术的问题的例子 -

从排序的数组中删除重复的内容

寻找链表中的 "第N "个节点

二和二 - 输入的数组已被排序

两相和III--输入数组已被排序

反转字符串中的字II

旋转数组

有效复数

有最多水的容器

除自己之外的数组的乘积

双指针技术是如何工作的？

起点和终点指针 -> 左边和右边的指针。

一个指针从头开始，另一个指针从尾开始，直到它们相遇。

慢速指针和快速指针:

一个慢速运行器（以较慢的速度移动），另一个快速运行器（移动速度是慢速指针的两倍）。

图片来源：codebus

双指针编程中的重要模式和技术问题

1.终端指针--左和右指针

在左、右指针的情况下，从第一个元素开始，每次迭代左指针的一个元素，从末端迭代右元素。评估条件并相应地增加或减少指针。

2. 左和右指针--滑动窗口

左边和右边的指针从第一个元素开始，按照要求不断滑动（即基于目标条件）。

3. 慢速和快速指针

慢速指针移动一个元素，快速指针移动两倍的速度，即从数组的第一个索引开始移动两个元素，直到它们相遇。

模式→以下问题属于双指针技术（不限于此）。

在一个链接列表的M个节点之后删除N个节点

删除一个关联列表的中间节点

从排序的数组中删除重复的内容

双和法II--输入数组被排序

反转字符串中的字数II

旋转数组

有效复数

有最多水的容器

除自己之外的数组的乘积等

最重要的问题与解决方案 注：每天都会有新的基于两个指针技术的问题和解决方案被添加。所以每天都要检查这个帖子。

黄金法则是--通过做/实施来学习

在这里，我们将看到最重要的基于双指针技术的问题。

装有大量水的容器 问题 -

给你一个长度为n的整数数组高度。有n条垂直线，其中第1条线的两个端点是（i，0）和（i，高度[i]）。

找出两条线，它们与x轴一起构成一个容器，使该容器中的水最多。

返回一个容器所能储存的最大水量。

例子:

输入：height = [1,8,6,2,5,4,8,3,7] 。
输出：49
1

解决方案:

主要逻辑/想法 -

主要的逻辑是取两个指针左（数组的开始）和右（容器高度的结束）和一个maxarea变量来存储当前的面积。计算面积并更新maxarea的指针。

如果左指针所指向的高度小于右指针所指向的高度，则不断增加左指针/减少右指针。持续更新最大面积。

主要逻辑 实现 -

def maxArea(self, height: List[int]) -> int:
        left,right,ans = 0,len(height)-1, 0
        
        while left < right :
            ar = (right- left) * min(height[left],height[right])
            ans = max(ans,ar)
            
            if height[left] < height[right]:
                left +=1
            else:
                right -=1
        return ans
1

问题链接

类似的模式--

最小不相容性

计算符合规则的项目

破碎的计算器

从列表的末尾删除第N个节点 问题 -

给出一个链接列表的头部，从列表的末端移除第n个节点并返回其头部。

例子:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
1

解决方案 :

主要逻辑/想法 -

主要思路是--取两个指针并不断递增，直到找到目标节点之前的一个节点（左边的指针），而右边的指针将一直走到最后，以存储要删除的节点所指向的下一个节点的地址。一旦完成，将left.next指向left.next.next来删除目标节点。

主要逻辑 实现 -

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        temp =ListNode(0,head)
        left = temp
        right = head
        
        while n>0 and right:
            right = right.next
            n -=1
            
        while right:
            left =left.next
            right = right.next
        
        left.next = left.next.next
        return temp.next
1

问题链接

类似的模式--

在一个关联列表的M个节点之后删除N个节点

删除关联列表中的中间节点

交换关联列表中的节点

链接列表循环 问题 -

给出头，即一个链表的头，确定该链表中是否有一个循环。

如果列表中存在一些节点，可以通过持续跟踪下一个指针再次到达，那么链接列表中就有一个循环。在内部，pos被用来表示tail的下一个指针所连接的节点的索引。注意，pos不作为一个参数传递。

如果在链表中有一个循环，返回true。否则，返回 false。

例子 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
1

解决方案。

主要逻辑/想法 -

主逻辑--取两个指针，一个是慢速的X速度，另一个是快速的2倍速度。从第一个节点开始遍历，将慢速指针增加一个节点，快速指针增加两个节点。如果慢速指针遇到快速指针，则返回True（即循环存在于链表中），否则返回False。

主要逻辑 实现 -

def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head
        
        while fast and fast.next :
            slow= slow.next 
            fast = fast.next.next 
            if slow == fast:
                return True 
        return False
1

问题链接：