双指针法

2.1 双指针法的定义。

双指针法 是一种用于解决数组和字符串各种问题的技巧，它使用两个指针（索引），这些指针可以根据特定规则在数据上移动。这个方法对寻找满足给定条件的元素对、子集问题特别有效。

这个方法通常是将两个指针初始化在数据结构的相对两端，然后根据特定规则移动它们。双指针法可以显著减少算法的时间复杂度，相比一些更简单的方法更高效。

主要原则

1. 初始化两个指针：指针可以被设置在数组或字符串的开始和结束，或根据问题需求设置在不同的索引。
2. 移动指针：指针根据特定规则移动（例如，两个指针都向中心移动，或一个指针向前移动，另一个保持不动）。
3. 检查条件：每一步都要检查条件，这个条件决定了是否继续移动指针或结束算法。

时间复杂度：

O(n) — 在大多数情况下，因为两个指针在数组上移动一次或更多次，总共不会超过O(n)次迭代。

对于某些问题，基于条件和指针的初始位置，时间复杂度可能是O(n log n)或O(n^2)，但这很少见。

用双指针法解决的问题示例：

2.2 找出数组中两个数，它们的和等于给定的数。

问题:

解决方案:

初始化一个指针在数组的开头，另一个在结尾。检查指针指向的元素之和：

• 如果和等于 target，返回索引。
• 如果和小于 target，向右移动左边的指针。
• 如果和大于 target，向左移动右边的指针。

时间复杂度: O(n).

Python代码示例：

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return left, right
        elif s < target:
            left += 1
        else:
            right -= 1
    return None
        

2.3 验证回文

问题:

检查一个字符串是否是回文。

解决方案:

初始化两个指针在字符串的开始和结束。比较指针对应的字符：

• 如果字符相同，向对方移动两个指针。
• 如果字符不同，字符串不是回文。

时间复杂度: O(n).

Python代码示例：

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
        

2.4 从排序数组中删除重复项

问题:

从排序数组中删除重复项。

解决方案:

使用两个指针，一个用于结果数组的当前位置，另一个用于遍历所有元素：

• 如果当前元素不等于前一个元素，将其写入结果数组。

时间复杂度: O(n).

Python代码示例：

def remove_duplicates(arr):
    if not arr:
        return 0
    write_index = 1
    for i in range(1, len(arr)):
        if arr[i] != arr[i - 1]:
            arr[write_index] = arr[i]
            write_index += 1
    return write_index