Two Pointers (双指针)

Two Pointers（双指针）是一种常用的技巧，主要用来处理数组或链表相关的问题。它的基本思路是使用两个指针（通常是数组或链表的索引）来同时操作数据，通过不同的指针间的关系来优化问题的解决方案。

什么时候用到双指针？

双指针技巧通常用于以下场景：

• 在一个数组或链表中寻找两个元素满足某个条件。
• 处理连续子数组、子串相关的问题。
• 解决需要快速扫描、处理数据问题的场景。

基本思想

通过使用两个指针，你可以在一个数据结构中以更有效的方式进行搜索、比较或拆分数据。常见的两种指针操作是：

1. 指针从两端向中间逼近。
2. 两个指针在数组的同一方向上滑动。

1. 从两端向中间逼近：常用于解决一些对称的问题

这种方式常见于排序数组中寻找满足条件的两个元素的和等问题。

举个例子：

假设我们有一个排序好的数组，[1, 2, 3, 4, 5, 6]，我们要找出两个元素的和为7的元素对。

可以用双指针来解决这个问题：

• 初始化一个指针指向数组的开头（left = 0），另一个指针指向数组的结尾（right = len(arr) - 1）。
• 计算当前两指针指向的元素的和：
  • 如果和等于目标值（比如7），那就找到了答案。
  • 如果和小于目标值，说明左指针的值太小，应该将左指针向右移动（left++），使和变大。
  • 如果和大于目标值，说明右指针的值太大，应该将右指针向左移动（right--），使和变小。
• 一直重复这个过程，直到两个指针相遇，或者找到符合条件的元素对。

代码示例：

def two_sum(arr, target):
    left, right = 0, len(arr) - 1
    
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return (arr[left], arr[right])  # 找到目标和
        elif current_sum < target:
            left += 1  # 让和变大
        else:
            right -= 1  # 让和变小
    
    return None  # 没有找到符合条件的元素

2. 两个指针在同一方向上滑动：常用于处理子数组或子串问题

这种方式常见于滑动窗口问题，通常用来找出连续子数组或子串。

举个例子：

假设你要找出一个数组中，和不超过某个值的最长子数组的长度。你可以用双指针来滑动窗口。

• 一个指针指向窗口的开始，另一个指针指向窗口的结束。
• 移动结束指针扩展窗口，直到窗口的和超过了目标值。
• 然后移动开始指针收缩窗口，直到窗口的和小于等于目标值。
• 在此过程中，记录下窗口的最大长度。

代码示例：

def max_subarray_length(arr, target):
    left = 0
    current_sum = 0
    max_len = 0
    
    for right in range(len(arr)):
        current_sum += arr[right]
        
        # 当和大于目标值时，收缩窗口
        while current_sum > target:
            current_sum -= arr[left]
            left += 1
        
        # 记录最大子数组长度
        max_len = max(max_len, right - left + 1)
    
    return max_len

双指针的优势

1. 优化时间复杂度：用双指针可以将一些O(n^2)的问题（例如暴力枚举两个元素的和）优化成O(n)的算法，因为每个元素最多被指针访问两次。
2. 减少空间复杂度：通常双指针不需要额外的存储空间，它直接在原数组或链表上操作，因此节省了空间。

总结

双指针是一种非常有效的技巧，广泛应用于数组、链表等数据结构的操作中。它的基本思路是同时使用两个指针，根据具体问题的需求，通过调整指针的位置来优化问题的解决过程。双指针技巧可以帮助你减少时间复杂度，提高算法的效率，解决许多实际问题。

LeetCode 相关题目:

LeetCode 双指针问题列表

已完成题目:

• 11. Container With Most Water