双指针主要分两类: 快慢指针和左右指针
快慢指针对于链表问题, 我们一般可以使用快慢指针解决
所谓的快慢指针是指, 使用两个指针按照不同的速度前进, 有两个指针我们可以确定:
链表是否有环
链表的倒数第k个节点
一些题目比如: 141题环形链表
注意: 两个指针相遇则有环 (类比在操场跑步, 速度不相等总能相遇)
代码
class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: if not head: return False fast_node = head.next slow_node = head while fast_node and fast_node.next: if slow_node == fast_node: return True fast_node = fast_node.next.next slow_node = slow_node.next return False又比如:
142题环形链表 II
142题环形链表 II 的题解
左右指针左右指针一般的形式就是我们常说的二分查找(二分搜索)
一般的使用方式:
def binary_search(nums: List[int], target: int): left = 0 right = ... while ...: mid = left + (right - left) / 2 if nums[mid] == target: ... elif nums[mid] < target: left = ... elif nums[mid] > target: right = ... return ...我们需要的注意点为...部分:
前两个...有由搜索区间决定, 即问题为[left : right]或[left : right)
[left: right]: right = len(nums) - 1和while left <= right
[left: right): right = len(nums) 和while left < right
前者的结束条件为: [right + 1 : right](如: [3 : 2])
后者的结束条件为: [left : right](如: [2 : 2])
后面的...由题目决定
nums[mid] == target: 返回某个值的问题, 直接返回; 返回边界的问题, 缩小边界(right = mid或left = mid)
nums[mid] > target: 太大了, 一般为缩小右边界:right = mid - 1
nums[mid] < target: 太小了, 一般为缩小左边界:left = mid + 1
对于一些问题, 我们可以将问题的区间统一为[left : right], 即right = len(nums) - 1和while left <= right
比如:
返回某个值的问题
在leetcode上对应的题目:704.二分查找（简单） 题解
返回左边界的问题
def left_bound(nums: List[int], target: int): left = 0 right = len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] < target: left = mid + 1 elif nums[mid] > target: right = mid - 1 elif nums[mid] == target: # 别返回，锁定左侧边界 right = mid - 1 # 最后要检查 left 越界的情况 # left可能超出范围 即 >= len(nums) if left >= len(nums) or nums[left] != target: return -1 return left结束条件为: [right + 1 : right](如: [3 : 2])
返回左边界left
返回右边界的问题
def right_bound(nums: List[int], target: int): left = 0 right = len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] < target: left = mid + 1 elif nums[mid] > target: right = mid - 1 elif nums[mid] == target: # 别返回，锁定右侧边界 left = mid + 1 # 最后要检查 right 越界的情况 if right < 0 or nums[right] != target: return -1 return right结束条件为: [right + 1 : right](如: [3 : 2])
返回右边界right
在leetcode上对应的题目:
707. 在排序数组中查找元素的第一个和最后一个位置（中等）
在排序数组中查找元素的第一个和最后一个位置 的题解
滑动窗口滑动窗口是双指针的一种, 也可以说是左右指针的一种
其主要解决的是子串问题
所谓的子串问题是指: 一个长的字符串是否全部包含 一个短的字符串 (包括数量)
滑动窗口的思想:
① 我们可以设两个指针, 分别对应窗口的左右边界
② 右边界向右扩大窗口, 直到找到符合条件的子串
③ 左边界向右缩小窗口, 更新数据, 根据题目是否返回
④ 假如还未返回, 则重复②和③
⑤ 根据题目是否返回
模板:
def sliding_window(s: str, t: str): """ :param s 大的字符串 :param t 小的字符串 :return 根据题目返回 """ need = {} # 存放需要的字符数 windows = {} # 存放当前窗口中的字符数 # 记录需要的字符数 for char in t: # 需要字符的数量自增1 need[char] = need.setdefault(char, 0) + 1 # setdefault作用字典中不存在字符时, 返回0 # 左右边界的指针 left = right = 0 # 用于记录已经通过检验的字符数 valid = 0 """ 假如有其他变量可以在这里添加 """ while right < len(s): # right_char为将要移入的窗口字符 right_char = s[right] # 右移窗口 right += 1 # 假如当前 右边界 的字符,为需要的字符 if right_char in need: """ 更新数据 一般是 1. 当前窗口的数据 2. 通过的 字符数 """ # 记录当前窗口符合要求的字符数量 windows[right_char] = windows.setdefault(right_char, 0) + 1 # 假如当前字符已经符合要求 # 通过检验的字符数 + 1 if windows[right_char] == need[right_char]: valid += 1 # 判断左边界是否可以收缩 # !!!! 这个条件根据题目而变 while condition: """ 根据题目是否在这里返回 """ # left_char为将要移出的窗口字符 left_char = s[left] left += 1 if left_char in need: """" 更新数据 一般是 1. 当前窗口的数据 2. 通过的 字符数 自定义的其他变量也在这里更新 """ # 假如当前字符已经符合要求 # 通过检验的字符数 - 1 if windows[left_char] == need[left_char]: valid -= 1 # 记录当前窗口符合要求的字符数量 - 1 windows[left_char] = windows.setdefault(left_char, 0) - 1 """ 根据题目是否在这里返回 """这个模板的主要注意点是
是否需要一些其他的变量, 如当前子串的长度
边界缩小的条件
什么时候返回
一些题目76. 最小覆盖子串（困难）的题解
567. 字符串的排列（中等）的题解
438. 找到字符串中所有字母异位词（中等）的题解
3. 无重复字符的最长子串（中等）的题解