双指针模板

一句话说明

双指针技巧主要用于数组和链表问题，通过两个指针的移动来优化时间复杂度。

套路拆解

• 对撞指针：核心是维护一个仍可能包含答案的闭区间。
• 快慢指针：fast 负责探索新元素，slow 负责维护有效结果区间。
• 滑动窗口：本质是“右扩张、左收缩”，始终维护一个合法连续区间。
• 三指针：通常先固定一个位置，再把剩余部分转成双指针问题。

适用场景

类型	适用场景	时间复杂度
对撞指针	有序数组、回文、两数之和	O(n)
快慢指针	链表环、数组去重、原地修改	O(n)
滑动窗口	子串、子数组问题	O(n)
三指针	三数之和、荷兰国旗	O(n²)

易错点

1. 对撞指针：通常需要数组有序
2. 快慢指针：注意边界条件，防止空指针
3. 滑动窗口：明确窗口何时扩大、何时收缩
4. 去重：使用while跳过重复元素

Go 代码

// 对撞指针
func twoSum(numbers []int, target int) []int {
    left, right := 0, len(numbers)-1
 
    for left < right {
        sum := numbers[left] + numbers[right]
 
        if sum == target {
            return []int{left + 1, right + 1}
        } else if sum < target {
            left++
        } else {
            right--
        }
    }
 
    return []int{}
}
 
// 快慢指针
func removeElement(nums []int, val int) int {
    slow := 0
 
    for fast := 0; fast < len(nums); fast++ {
        if nums[fast] != val {
            nums[slow] = nums[fast]
            slow++
        }
    }
 
    return slow
}
 
// 链表快慢指针
func hasCycle(head *ListNode) bool {
    if head == nil {
        return false
    }
 
    slow, fast := head, head
 
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
 
        if slow == fast {
            return true
        }
    }
 
    return false
}

---

返回：算法模板