跳转至

双指针算法详解

双指针是一种用两个变量在线性结构上遍历来解决问题的技巧。根据指针移动方向，分为 相向双指针（两指针从两端向中间移动）和 快慢指针（两指针同向移动，速度不同）。

适用场景

类型 场景 例题
相向双指针 有序数组查找、反转 两数之和、反转字符串
快慢指针 链表环检测、找中点 环形链表、链表中点
同向双指针 删除元素、子序列 删除倒数第N个节点

实战练习

相向双指针

🟢 344. 反转字符串

原地反转字符数组。

示例：["h","e","l","l","o"] → ["o","l","l","e","h"]

思路：左右指针相向移动，交换元素。

func reverseString(s []byte) {
    left, right := 0, len(s)-1
    for left < right {
        s[left], s[right] = s[right], s[left]
        left++
        right--
    }
}

🟢 977. 有序数组的平方

给定非递减数组，返回每个数的平方组成的新数组，也按非递减排序。

示例：[-4,-1,0,3,10] → [0,1,9,16,100]

思路：平方后最大值在两端。双指针从两端向中间，每次取较大的放入结果末尾。

func sortedSquares(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    left, right := 0, n-1

    for pos := n - 1; pos >= 0; pos-- {
        l2, r2 := nums[left]*nums[left], nums[right]*nums[right]
        if l2 > r2 {
            result[pos] = l2
            left++
        } else {
            result[pos] = r2
            right--
        }
    }
    return result
}

🟡 167. 两数之和 II（输入有序数组）

在有序数组中找两个数，使它们的和等于 target。

示例：numbers = [2,7,11,15], target = 9 → [1,2]

思路：双指针从两端开始，和太大右指针左移，和太小左指针右移。

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{-1, -1}
}

快慢指针（链表）

🟢 141. 环形链表

判断链表是否有环。

思路：快指针每次走两步，慢指针每次走一步。如果有环，快慢指针必然相遇。

func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }

    slow, fast := head, head.Next
    for fast != slow {
        if fast == nil || fast.Next == nil {
            return false
        }
        slow = slow.Next
        fast = fast.Next.Next
    }
    return true
}

🟢 876. 链表的中间结点

返回链表的中间结点。若有两个中间结点，返回第二个。

示例：[1,2,3,4,5] → 返回结点 3

思路：快指针每次走两步，慢指针每次走一步。快指针到达末尾时，慢指针正好在中间。

func middleNode(head *ListNode) *ListNode {
    slow, fast := head, head

    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

🟡 19. 删除链表的倒数第 N 个结点

删除链表的倒数第 n 个结点，返回头结点。

示例：[1,2,3,4,5], n=2 → [1,2,3,5]

思路：快指针先走 n 步，然后快慢指针同时走。快指针到末尾时，慢指针指向待删除节点的前一个。

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}  // 哨兵节点，处理删除头结点的情况
    slow, fast := dummy, dummy

    // 快指针先走 n+1 步
    for i := 0; i <= n; i++ {
        fast = fast.Next
    }

    // 同时移动，直到快指针到末尾
    for fast != nil {
        slow = slow.Next
        fast = fast.Next
    }

    // 删除节点
    slow.Next = slow.Next.Next
    return dummy.Next
}

其他双指针

🟢 392. 判断子序列

判断 s 是否是 t 的子序列（保持相对顺序）。

示例：s = "abc", t = "ahbgdc" → true

思路：两个指针分别遍历 s 和 t，字符相同时 s 指针后移。

func isSubsequence(s string, t string) bool {
    i, j := 0, 0

    for i < len(s) && j < len(t) {
        if s[i] == t[j] {
            i++
        }
        j++
    }
    return i == len(s)
}

🟡 189. 轮转数组

将数组向右轮转 k 个位置。

示例：[1,2,3,4,5,6,7], k=3 → [5,6,7,1,2,3,4]

思路：三次反转——整体反转，前 k 个反转，后 n-k 个反转。

func rotate(nums []int, k int) {
    k %= len(nums)
    reverse(nums)           // 整体反转
    reverse(nums[:k])       // 前 k 个反转
    reverse(nums[k:])       // 后 n-k 个反转
}

func reverse(nums []int) {
    left, right := 0, len(nums)-1
    for left < right {
        nums[left], nums[right] = nums[right], nums[left]
        left++
        right--
    }
}

🟢 557. 反转字符串中的单词 III

反转字符串中每个单词的字符顺序。

示例："Let's take LeetCode contest" → "s'teL ekat edoCteeL tsetnoc"

func reverseWords(s string) string {
    bytes := []byte(s)
    start := 0

    for i := 0; i <= len(bytes); i++ {
        if i == len(bytes) || bytes[i] == ' ' {
            reverse(bytes[start:i])
            start = i + 1
        }
    }
    return string(bytes)
}

func reverse(s []byte) {
    left, right := 0, len(s)-1
    for left < right {
        s[left], s[right] = s[right], s[left]
        left++
        right--
    }
}

🟢 2000. 反转单词前缀

找到字符 ch 第一次出现的位置，反转从开头到该位置的子串。

示例：word = "abcdefd", ch = "d" → "dcbaefd"

func reversePrefix(word string, ch byte) string {
    bytes := []byte(word)

    for i := 0; i < len(bytes); i++ {
        if bytes[i] == ch {
            // 反转 [0, i]
            left, right := 0, i
            for left < right {
                bytes[left], bytes[right] = bytes[right], bytes[left]
                left++
                right--
            }
            break
        }
    }
    return string(bytes)
}

总结

技巧 适用场景 关键点
相向双指针 有序数组、反转 从两端向中间逼近
快慢指针 链表环、中点 速度差产生距离
同向双指针 删除、子序列 一个遍历，一个记录

练习建议

双指针的核心在于「边界处理」。建议画图模拟指针移动过程，理解终止条件。

评论