双指针法是一种常用且有效的算法技巧，主要用于数组、链表等线性数据结构的处理，我们来系统地梳理一下：

1. 双指针法的基本概念

双指针法使用两个指针在（线性）数据结构中移动，以完成特定任务。根据移动方向和起始位置，可以分为以下几类：

• 同向双指针(快慢指针)
• 相向双指针
• 背向双指针

2. 同向双指针(快慢指针)

• 两个指针从同一侧开始，通常都从左侧开始。
• 一个指针移动较快，另一个指针移动较慢。
• 常用于解决数组中的重复元素、链表中的循环检测等问题。

示例: 删除排序数组中的重复项

from typing import List


def remove_duplicates(nums: List[int]) -> int:
    if len(nums) == 0:
        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

示例：删除链表中指定的元素项

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    dummy := &ListNode{Next: head}
    prev := dummy
    curr := prev.Next
    for curr != nil {
        if curr.Val == val {
            prev.Next = curr.Next
        } else {
            prev = curr
        }
        curr = curr.Next
    }
    return dummy.Next
}

示例：给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，元素的顺序可能发生改变，然后返回 nums 中与 val 不同的元素的数量。

func removeElements(nums []int, val int) int {
		fast := 0
		slow := fast
		for fast < len(nums) {
			if nums[fast] != val {
				nums[slow] = nums[fast]
				slow++
			}
			fast++
		}
		return slow
}

3. 相向双指针

• 两个指针分别从数组的两端向中间移动
• 常用于排序数组的搜索、求和问题等

示例: 两数之和 II - 输入有序数组

from typing import List


def two_sum(nums: List[int], target: int) -> List[int]:
    left, right = 0, len(nums) - 1

    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return [left + 1, right + 1]
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return []  # 未找到符合条件的两个数

4. 背向双指针

• 两个指针从中间向两端移动
• 常用于寻找最长回文子串等问题

示例: 最长回文子串

def longest_palindrome(s: str) -> str:
    def expand_around_center(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left+1:right]

    result = ""
    for i in range(len(s)):
        # 奇数长度回文
        odd = expand_around_center(i, i)
        # 偶数长度回文
        even = expand_around_center(i, i+1)
        result = max(result, odd, even, key=len)

    return result

5. 使用双指针的技巧

• 明确指针的含义和移动条件
• 注意边界条件的处理
• 在循环中正确地更新指针
• 考虑特殊情况(如空数组、单元素数组等)

6. 常见应用场景

• 数组/字符串的原地操作
• 滑动窗口问题
• 链表操作(如找中点、检测环)
• 回文串问题
• 归并两个有序数组

双指针法的核心在于利用问题的特性，通过巧妙设置和移动两个指针来降低时间复杂度，通常可以将暴力解法的 O(n^2) 优化到 O(n)。