跳到主要内容

双指针技巧

介绍

双指针技巧是一种在算法中常用的策略,通过使用两个指针(通常是索引或引用)来遍历数据结构(如数组或链表),从而高效地解决问题。双指针技巧通常用于优化时间复杂度,减少不必要的计算。

双指针技巧主要有两种类型:

  1. 快慢指针:两个指针以不同的速度移动,常用于检测链表中的环或找到链表的中间节点。
  2. 左右指针:两个指针从数据结构的左右两端向中间移动,常用于解决数组中的问题,如两数之和或反转数组。

快慢指针

快慢指针是一种常见的双指针技巧,通常用于链表相关的问题。快指针每次移动两步,而慢指针每次移动一步。通过这种方式,可以检测链表是否有环,或者找到链表的中间节点。

示例:检测链表中的环

假设我们有一个链表,我们需要检测链表中是否存在环。我们可以使用快慢指针来解决这个问题。

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]

提示

在这个例子中,我们使用左右指针来遍历数组。如果当前和小于目标值,左指针向右移动;如果当前和大于目标值,右指针向左移动。

实际应用场景

双指针技巧在实际应用中有广泛的用途,以下是一些常见的应用场景:

  1. 反转数组:使用左右指针可以高效地反转数组。
  2. 删除排序数组中的重复项:使用快慢指针可以在原地删除数组中的重复项。
  3. 判断回文字符串:使用左右指针可以判断一个字符串是否是回文。

示例:反转数组

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]

警告

在反转数组时,左右指针分别从数组的两端向中间移动,交换它们所指向的元素。

总结

双指针技巧是一种非常高效的算法策略,适用于多种数据结构(如数组和链表)的问题。通过使用快慢指针或左右指针,我们可以优化时间复杂度,减少不必要的计算。

附加资源

练习

  1. 使用双指针技巧解决 LeetCode 167. 两数之和 II - 输入有序数组
  2. 使用双指针技巧解决 LeetCode 141. 环形链表
  3. 使用双指针技巧解决 LeetCode 344. 反转字符串

通过练习这些题目,你将更好地掌握双指针技巧,并能够在实际问题中灵活运用。