双指针主要应用于遍历数组，两个指针指向不同的元素，协同完成任务；常见的指针类型有左右指针与快慢指针。
左右指针的应用较为广泛，一般数组多为有序数组，其中二分查找（元素查找）与滑动窗口算法涉及的题目较多，后续将对这两个算法进行详细介绍。本小节重点介绍左右指针的其他应用，如两数之和、反转数组、去除指定元素等。 【通用题解】 ① 元素搜索 通常两个指针为反向，即初始化为0与len(nums)-1；此时待搜索数组一般为有序数组。 左右遍历数组，满足条件时返回结果；不满足条件，则依据目标任务更新左指针（left+1）或右指针(right-1)。 ② in-place修改数组 通常用于移动数组元素，为优化逐元素移动的复杂度，引入双指针，通过交换左右指针指向的元素，直接将满足/不满足要求的元素移至前端/末端。
题目描述： 解题思路： 设置左右指针： ① 若两数之和与目标值相等，则返回左右指针的索引（+1）； ② 若两数之和小于目标值，则左指针+1；否则，右指针-1。
代码实现：
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: left, right = 0, len(nums)-1 while left < right: sum_i = nums[left] + nums[right] if sum_i == target: return [left+1, right+1] elif sum_i < target: left += 1 else: right -= 1题目描述： 解题思路： 设置同向双指针：从后往前对两数组进行比较 若从前往后进行比较，则前面每增加一个元素，其后边的元素相应地均需往后移动一位；因此优先满足末端元素的排序，同时也考虑到数组nums1后n位数字为0，直接覆盖后n位数字，不会影响nums1前m位本身的顺序。 ① 若指向nums2的索引t2小于0，则说明nums2已经全部遍历，直接返回结果； ② 若指向nums1的索引t1小于0；或者nums1[t1] < nums2[t2]，则替换值为nums[t2]，此时nums2[t2]已经遍历，因此索引t2减1；否则替换值为nums1[t1]，索引t1减1。
代码实现：
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. """ t1, t2 = m-1, n-1 i = m+n-1 while i >= 0: if t2 < 0: return else: if nums1[t1] < nums2[t2] or t1 < 0: nums1[i] = nums2[t2] t2 -= 1 else: nums1[i] = nums1[t1] t1 -= 1 i -= 1题目描述： 解题思路： 简单直接的解法：for循环遍历，若在数组中，则添加至结果数组；否则，继续进行遍历。此时空间复杂度为O(n)。 优化空间复杂度为O(1)：设置左右指针，若元素满足条件（即需要移除的元素），则将左右指针对应的元素进行交换，即可将val直接移至最末端。
class Solution: def removeElement(self, nums: List[int], val: int) -> int: i, j = 0, len(nums)-1 while i < j: if nums[i] == val: nums[i] = nums[j-1] j -= 1 else: i += 1 # print(i, j, nums) return j① 3sum 4sum ② 去除指定元素II （参考题目3）
快慢指针最经典的应用便是寻找链表中的环了，可扩展为寻找链表环的起点，同时链表的应用还有寻找链表中点、倒数第K个元素等。除此之外，快慢指针可看作同向指针，可应用于归并两个数组。
【通用题解】 链表：快慢指针一般均初始化指向链表的头结点head，前进时fast指针在前，慢指针slow在后；通过设计fast指针的步长（1、2或K）来找到目标结点的位置。 数组：同向指针初始化索引值均为0或len(nums)-1。
题目描述： 解题思路： 单链表的特点是每个节点只知道下一个节点，因此一个指针的话无法判断链表中是否含有环的，此时则需双指针来进行判断。 ① 链表中不含环：快指针最终会遇到空指针null，则可说明该链表不含环。 ② 链表中含有环：若仅使用单指针就会陷入死循环，因为环形数组中没有 null 指针作为尾部节点。 经典解法就是用两个指针，快指针步长为2，慢指针步长为1，快指针会超慢指针，并和慢指针相遇，则说明链表含有环。
代码实现：
class Solution: def hasCycle(self, head: ListNode) -> bool: if not head or not head.next: return False slow = head fast = head.next while slow != fast: if not fast or not fast.next: return False slow = slow.next fast = fast.next.next return True题目描述：
解题思路： 代码实现：
class Solution: def detectCycle(self, head: ListNode) -> ListNode: if not head: return None fast = slow = head # 初始化快慢指针 while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: fast = head while fast: if slow == fast: return slow slow = slow.next fast = fast.next return None题目描述： 解题思路： 设计快慢指针，快指针步长为2，慢指针步长为1，则当快指针走完整个链表时，慢指针正好指向链表的中点。
代码实现：
class Solution: def middleNode(self, head: ListNode) -> ListNode: fast = slow = head while fast and fast.next: fast = fast.next.next slow = slow.next return slow① 寻找链表倒数第k个数（剑指offer-面试题22） ② 寻找重复数字 数组中仅有一个重复元素！则可看作题目2（寻找环的起点）的变形，重复数字便可看作环的起点。
