LeetCode入门计划 | 双指针（Python3）

• 前言
• 一、双指针——普通指针
• 二、双指针——对撞指针
• 三、双指针——快慢指针
• 总结

双指针是算法入门，用于处理数组，字符串等问题。我们今天来学习学习它。并用对应的例题来实践一下。

就是两个指针往一个方向移动。常见的就是两个for 循环的嵌套了。

题目：

这题的解法有很多，但我们只使用普通指针的解法。
解题思路: 两个for循环

			#该方法能过测试的方法
 def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if nums[i]+nums[j]==target:
                    return [i,j]
        return []

对撞指针，就是指针初始化时，在数组的两遍，然后想中间移动。“对撞”。

题目：盛最多水的容器

解题思路：用对撞指针的思路，初始化左指针 left=0，右指针right=n-1
固定大的一边 移动小的一边去寻找最优解。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        """
        # 该题 使用对撞指针解法。
        # 固定大的一边 移动小的一边去寻找最优解
        """
        # 初始化左右指针
        left = 0   # 左指针
        right = len(height)-1   # 右指针
        max_value =0            #最大值
        while left <=right:   # 对撞指针还没撞到一起时循环
            if height[right]  
三、双指针——快慢指针 
快慢指针，顾名思义就是将指双指针分为快指针和慢指针，并朝同一个方向移动。例如快指正移动两格，慢指针移动一格。分出快慢即可。图与普通双指针一致，只是移动速度不一样。
 题目：环形链表
 
 
  
 
解题思路：设置两指针，快指针每次移动两次，慢指针每次移动一次。当出现有环的情况，慢指针就会追到块指针（快慢指针指向地址相等）。
 
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        """
        # 利用快慢指针解题
        # 解题思路：块指针移动两个 慢指针移动一次，慢追上快 为True
        """
        # 做非空判断
        if head==None or head.next==None:
            return False
        
        s = head
        f = head

        while f.next!=None and f.next.next!=None:
            s = s.next #慢指针移动一次
            f = f.next.next #块指针移动两次
            if s.next == f.next:
                return True
        
        return False
 
总结 
双指针入门计划，指针可以是下标，可以是链表的next指针。其实就是用所以来遍历序列解决不同的问题。