一、双指针算法概念

双指针算法是一种常用的算法技巧，通过使用两个指针在数据结构（如数组、链表等）中协同工作，来解决一些特定问题。它的核心思想是通过指针的移动来减少时间复杂度，通常用于优化暴力解法。

---

二、双指针的常见应用场景

1. 数组或链表中的遍历：

   • 通过两个指针从不同方向或相同方向遍历，解决一些查找或匹配问题。

2. 滑动窗口：

   • 通过两个指针维护一个窗口，解决子数组或子字符串的相关问题。

3. 快慢指针：

   • 通过两个指针以不同速度移动，解决环形链表或中点查找问题。

4. 有序数组的两数之和：

   • 通过两个指针从两端向中间移动，解决有序数组中的两数之和问题。

---

三、双指针的基本思想

1. 指针的初始化：

   • 根据问题需求，初始化两个指针的位置。例如，一个指向开头，一个指向结尾；或者两个都指向开头。

2. 指针的移动规则：

   • 根据问题的条件，决定指针的移动方向。例如，左指针向右移动，右指针向左移动，或者快指针移动两步，慢指针移动一步。

3. 终止条件：

   • 当两个指针满足某种条件时（如相遇、超出范围等），算法终止。

---

四、双指针的流程图

以下是双指针算法的通用流程图，使用 Mermaid 语法绘制：

流程图说明

1. 开始：

• 算法开始执行。

2. 初始化指针：

• 根据问题需求，初始化两个指针的位置。

3. 是否满足终止条件?：

• 检查当前指针是否满足终止条件（如相遇、超出范围等）。

• 如果满足，则算法结束。

• 如果不满足，则继续执行。

4. 处理当前指针位置：

• 根据当前指针的位置，处理数据（如计算和、判断条件等）。

5. 根据条件移动指针：

• 根据问题的条件，移动指针（如左指针右移、右指针左移等）。

6. 结束：

• 算法终止，返回结果。

---

五、双指针的常见类型

1. 同向双指针

• 两个指针从同一侧开始，按照相同方向移动。
• 适用于滑动窗口问题或链表遍历问题。
• 例如：在一个数组中，找到满足条件的最短子数组。

2. 对向双指针

• 两个指针从两端开始，向中间移动。
• 适用于有序数组的查找问题。
• 例如：在有序数组中，找到两个数之和等于目标值。

3. 快慢指针

• 两个指针以不同速度移动。
• 适用于链表中的环检测或中点查找问题。
• 例如：判断链表是否有环，或找到链表的中点。

---

六、双指针的优势

1. 时间复杂度优化：

   • 双指针算法通常可以将时间复杂度从 O(n²) 优化到 O(n)。

2. 空间复杂度低：

   • 双指针算法通常只需要常数级别的额外空间（O(1)）。

3. 代码简洁：

   • 双指针算法的实现通常比暴力解法更简洁，逻辑更清晰。

---

七、双指针的注意事项

1. 边界条件：

   • 需要特别注意指针的初始位置和移动范围，避免越界。

2. 移动规则：

   • 指针的移动规则必须清晰明确，否则可能导致错误结果。

3. 终止条件：

   • 必须确保算法能够在正确的条件下终止，避免死循环。

---

八、双指针算法示例及代码

双指针算法是一种高效的算法技巧，常用于解决数组、链表等问题。以下是几个经典的双指针算法示例及其 Python 实现代码。

---

示例 1：有序数组的两数之和

A、问题描述

给定一个升序排列的数组和一个目标值，找到数组中两个数的和等于目标值，并返回它们的索引。

B、双指针思路

1. 初始化两个指针，一个指向数组开头（左指针），一个指向数组末尾（右指针）。
2. 计算左右指针指向的两个数的和。
3. 如果和等于目标值，返回结果。
4. 如果和小于目标值，左指针右移。
5. 如果和大于目标值，右指针左移。
6. 重复上述步骤，直到找到结果或指针相遇。

C、代码实现

def two_sum(nums, target):
    left, right = 0, len(nums) - 1  # 初始化左右指针
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return [left, right]  # 找到结果
        elif current_sum < target:
            left += 1  # 和太小，左指针右移
        else:
            right -= 1  # 和太大，右指针左移
    return []  # 未找到结果

# 示例
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))  # 输出: [0, 1]

示例 2：移除有序数组中的重复项

A、问题描述

给定一个升序排列的数组，原地移除重复的元素，并返回新数组的长度。

B、双指针思路

1. 初始化两个指针，一个慢指针（slow），一个快指针（fast）。

2. 快指针遍历数组，慢指针记录不重复元素的位置。

3. 当快指针指向的元素与慢指针指向的元素不同时，将快指针的元素复制到慢指针的下一个位置。

4. 最后返回慢指针的位置加 1，即为新数组的长度。

C、代码实现

def remove_duplicates(nums):
    if not nums:
        return 0
    slow = 0  # 慢指针
    for fast in range(1, len(nums)):  # 快指针
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1  # 新数组的长度

# 示例
nums = [1, 1, 2, 2, 3, 4, 4, 5]
length = remove_duplicates(nums)
print("新数组长度:", length)  # 输出: 5
print("新数组:", nums[:length])  # 输出: [1, 2, 3, 4, 5]

示例 3：判断链表是否有环

A、问题描述

给定一个链表，判断链表中是否有环。

B、双指针思路（快慢指针）

1. 初始化两个指针，一个慢指针（每次移动一步），一个快指针（每次移动两步）。

2. 如果链表中存在环，快指针最终会追上慢指针。

3. 如果快指针到达链表末尾（None），则链表中没有环。

C、代码实现

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def has_cycle(head):
    if not head or not head.next:
        return False
    slow, fast = head, head.next  # 初始化快慢指针
    while fast and fast.next:
        if slow == fast:
            return True  # 快指针追上慢指针，存在环
        slow = slow.next  # 慢指针移动一步
        fast = fast.next.next  # 快指针移动两步
    return False  # 快指针到达末尾，无环

# 示例
# 构造一个有环的链表
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2  # 形成环
print(has_cycle(node1))  # 输出: True

示例 4：滑动窗口的最大值

A、问题描述

给定一个数组和一个滑动窗口的大小，找到每个滑动窗口中的最大值。

B、双指针思路

1. 使用双指针维护一个滑动窗口。

2. 左指针表示窗口的起始位置，右指针表示窗口的结束位置。

3. 遍历数组，计算每个窗口的最大值。

C、代码实现

from collections import deque

def max_sliding_window(nums, k):
    if not nums or k == 0:
        return []
    result = []
    window = deque()  # 使用双端队列存储窗口中的索引
    for right in range(len(nums)):
        # 移除窗口中小于当前元素的索引
        while window and nums[window[-1]] < nums[right]:
            window.pop()
        window.append(right)  # 将当前元素索引加入窗口
        # 移除窗口左侧超出范围的索引
        if window[0] == right - k:
            window.popleft()
        # 当窗口大小达到 k 时，记录最大值
        if right >= k - 1:
            result.append(nums[window[0]])
    return result

# 示例
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(max_sliding_window(nums, k))  # 输出: [3, 3, 5, 5, 6, 7]

八、总结

  双指针算法是一种高效且灵活的算法技巧，适用于多种场景，如数组遍历、滑动窗口、链表操作等。
通过合理设计指针的初始位置、移动规则和终止条件，可以显著优化算法的时间复杂度和空间复杂度。
掌握双指针算法，能够帮助你更好地解决实际问题。

  双指针算法通过两个指针的协同工作，能够高效地解决数组、链表等问题。以下是双指针算法的核心要点：

1. 指针初始化：根据问题需求初始化指针的位置。

2. 指针移动规则：根据条件决定指针的移动方向。

3. 终止条件：确保算法在正确条件下终止。

  通过以上示例和代码，可以更好地理解和掌握双指针算法的应用。

© 著作权归作者所有