双指针技巧
介绍
双指针技巧是一种在算法中常用的策略，通过使用两个指针（通常是索引或引用）来遍历数据结构（如数组或链表），从而高效地解决问题。双指针技巧通常用于优化时间复杂度，减少不必要的计算。
双指针技巧主要有两种类型：
- 快慢指针：两个指针以不同的速度移动，常用于检测链表中的环或找到链表的中间节点。
- 左右指针：两个指针从数据结构的左右两端向中间移动，常用于解决数组中的问题，如两数之和或反转数组。
快慢指针
快慢指针是一种常见的双指针技巧，通常用于链表相关的问题。快指针每次移动两步，而慢指针每次移动一步。通过这种方式，可以检测链表是否有环，或者找到链表的中间节点。
示例：检测链表中的环
假设我们有一个链表，我们需要检测链表中是否存在环。我们可以使用快慢指针来解决这个问题。
python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def hasCycle(head):
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
输入：head = [3, 2, 0, -4]（链表形成一个环）
输出：True
备注
在这个例子中，快指针每次移动两步，慢指针每次移动一步。如果链表中存在环，快指针最终会追上慢指针。
左右指针
左右指针通常用于数组相关的问题。两个指针分别从数组的两端向中间移动，通过比较指针所指向的元素来解决问题。
示例：两数之和 II
给定一个已排序的数组和一个目标值，找到数组中两个数的和等于目标值，并返回它们的索引。
python
def twoSum(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum == target:
return [left + 1, right + 1]
elif current_sum < target:
left += 1
else:
right -= 1
return []
输入：numbers = [2, 7, 11, 15], target = 9
输出：[1, 2]
提示
在这个例子中，我们使用左右指针来遍历数组。如果当前和小于目标值，左指针向右移动；如果当前和大于目标值，右指针向左移动。
实际应用场景
双指针技巧在实际应用中有广泛的用途，以下是一些常见的应用场景：
- 反转数组：使用左右指针可以高效地反转数组。
- 删除排序数组中的重复项：使用快慢指针可以在原地删除数组中的重复项。
- 判断回文字符串：使用左右指针可以判断一个字符串是否是回文。
示例：反转数组
python
def reverseArray(nums):
left, right = 0, len(nums) - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
return nums
输入：nums = [1, 2, 3, 4, 5]
输出：[5, 4, 3, 2, 1]
警告
在反转数组时，左右指针分别从数组的两端向中间移动，交换它们所指向的元素。
总结
双指针技巧是一种非常高效的算法策略，适用于多种数据结构（如数组和链表）的问题。通过使用快慢指针或左右指针，我们可以优化时间复杂度，减少不必要的计算。
附加资源
练习
- 使用双指针技巧解决 LeetCode 167. 两数之和 II - 输入有序数组。
- 使用双指针技巧解决 LeetCode 141. 环形链表。
- 使用双指针技巧解决 LeetCode 344. 反转字符串。
通过练习这些题目，你将更好地掌握双指针技巧，并能够在实际问题中灵活运用。