高频算法题精讲-双指针与滑动窗口

章节导读

双指针和滑动窗口是算法面试中的高频考点,也是最实用的解题技巧之一。这两种技巧能把很多O(n²)的暴力解法优化到O(n),让你在面试中脱颖而出。

在大厂(字节、阿里、美团等)的算法面试中,双指针类题目的出现频率高达40%。掌握双指针技巧是算法面试的必备能力。

学习目标

  • 理解双指针的三种经典模式:对撞指针、快慢指针、滑动窗口
  • 掌握20+道LeetCode高频题的解题思路
  • 学会如何识别双指针题型
  • 理解时间复杂度优化的本质

一、双指针基础

1.1 什么是双指针

双指针不是数据结构,而是一种编程技巧。用两个指针(索引)在数组或链表上移动,替代嵌套循环。

暴力解法的问题:

// 找两数之和等于target,暴力双重循环O(n²)
for i := 0; i < n; i++ {
    for j := i+1; j < n; j++ {
        if arr[i] + arr[j] == target {
            return []int{i, j}
        }
    }
}

双指针优化:

// 如果数组有序,双指针O(n)
left, right := 0, n-1
for left < right {
    sum := arr[left] + arr[right]
    if sum == target {
        return []int{left, right}
    } else if sum < target {
        left++  // 和太小,左指针右移
    } else {
        right-- // 和太大,右指针左移
    }
}

1.2 双指针的三种模式

模式1:对撞指针(相向而行)

两个指针从数组两端出发,向中间靠拢。

left →              ← right
[1, 2, 3, 4, 5, 6, 7, 8]

典型题目:

  • 两数之和(有序数组)
  • 三数之和
  • 反转字符串
  • 验证回文串

模式2:快慢指针(同向而行)

两个指针从同一端出发,移动速度不同。

slow →  fast →
[1, 2, 3, 4, 5, 6, 7, 8]

典型题目:

  • 删除重复元素
  • 环形链表
  • 链表中点
  • 移除元素

模式3:滑动窗口(可变长度子数组)

维护一个窗口,通过移动左右边界来求解。

    [left...right]
[1, 2, 3, 4, 5, 6, 7, 8]

典型题目:

  • 最长无重复子串
  • 最小覆盖子串
  • 字符串排列
  • 找所有字母异位词

二、对撞指针

2.1 [LeetCode 167] 两数之和 II - 有序数组

这道题是双指针的入门题,也是面试高频题。

题目:

给定一个升序排列的数组,找出两个数使得它们的和等于target。
返回这两个数的索引(1-indexed)。

示例:
输入: numbers = [2,7,11,15], target = 9
输出: [1,2]
解释: 2 + 7 = 9

思路分析:

新手看到这题,第一反应是暴力双重循环:

for i := 0; i < len(numbers); i++ {
    for j := i+1; j < len(numbers); j++ {
        if numbers[i] + numbers[j] == target {
            return []int{i+1, j+1}
        }
    }
}
// 时间复杂度O(n²)

但面试官看到这个解法会皱眉,因为你没有利用数组有序这个关键信息。

有序数组的特性:

  • 左边的数小,右边的数大
  • 如果 arr[left] + arr[right] > target,说明和太大了,需要让和变小
  • 怎么让和变小?把right左移,换一个更小的数
  • 反之,如果和太小,就把left右移

完整代码:

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} // 题目要求1-indexed
        } else if sum < target {
            left++  // 和太小,需要更大的数
        } else {
            right-- // 和太大,需要更小的数
        }
    }

    return nil // 题目保证有解,这行其实不会执行
}

复杂度分析:

  • 时间复杂度:O(n),每个元素最多被访问一次
  • 空间复杂度:O(1),只用了两个指针

为什么这个算法正确?

很多人会问:万一跳过了正确答案怎么办?

证明:假设正确答案是 numbers[i] + numbers[j] = target,其中 i < j。

  1. 初始状态:left=0, right=n-1
  2. 如果 i 在 left 右边,那么 left 一定会移动到 i
  3. 如果 j 在 right 左边,那么 right 一定会移动到 j
  4. 当 left=i 且 right=j 时,算法会返回答案

不会跳过的原因:

  • 如果当前和 < target,left右移不会错过答案,因为当前right对应的数太小了
  • 如果当前和 > target,right左移不会错过答案,因为当前left对应的数太大了

2.2 [LeetCode 15] 三数之和

这道题是字节、阿里的高频题,难度中等,但很多人容易写出bug。

题目:

给定一个数组,找出所有和为0的三元组,且不能包含重复的三元组。

示例:
输入: nums = [-1,0,1,2,-1,-4]
输出: [[-1,-1,2],[-1,0,1]]

思路分析:

三数之和看起来需要三重循环O(n³),但我们可以优化到O(n²)。

核心思路:把三数之和转化为两数之和。

固定一个数nums[i],然后在剩余数组中找两数之和 = -nums[i]

步骤:

  1. 先排序(重要!)
  2. 固定第一个数 nums[i]
  3. 用双指针在 [i+1, n-1] 范围内找两数之和 = -nums[i]
  4. 去重处理

完整代码:

func threeSum(nums []int) [][]int {
    result := [][]int{}
    n := len(nums)

    if n < 3 {
        return result
    }

    // 1. 排序
    sort.Ints(nums)

    // 2. 固定第一个数
    for i := 0; i < n-2; i++ {
        // 优化1:如果第一个数>0,后面都是正数,不可能和为0
        if nums[i] > 0 {
            break
        }

        // 去重1:第一个数去重
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }

        // 3. 双指针找两数之和 = -nums[i]
        target := -nums[i]
        left, right := i+1, n-1

        for left < right {
            sum := nums[left] + nums[right]

            if sum == target {
                result = append(result, []int{nums[i], nums[left], nums[right]})

                // 去重2:第二个数去重
                for left < right && nums[left] == nums[left+1] {
                    left++
                }
                // 去重3:第三个数去重
                for left < right && nums[right] == nums[right-1] {
                    right--
                }

                left++
                right--
            } else if sum < target {
                left++
            } else {
                right--
            }
        }
    }

    return result
}

关键点:

  1. 为什么要排序?

    • 方便去重
    • 可以用双指针优化

  2. 去重逻辑:

    [-1, -1, 0, 1, 2, -1, -4]
排序后:[-4, -1, -1, -1, 0, 1, 2]

当i=1时,nums[i]=-1
当i=2时,nums[i]=-1,和i=1重复,跳过

  3. 时间复杂度:

    • 排序:O(n log n)
    • 双重循环:O(n²)
    • 总时间:O(n²)

常见错误:

// 错误1:去重位置错误
if nums[i] == nums[i-1] { // 缺少 i > 0 判断,会数组越界
    continue
}

// 错误2:忘记去重
// 会导致结果中有重复的三元组,比如[[-1,0,1], [-1,0,1]]

// 错误3:去重逻辑错误
if i > 0 && nums[i] == nums[i+1] { // 应该和前一个比较,不是后一个
    continue
}

2.3 [LeetCode 11] 盛最多水的容器

这道题是腾讯、美团的高频题,很多人第一次做会卡住。

题目:

给定数组height,每个元素代表一条竖线的高度。
找两条线与x轴构成的容器,使得容器能容纳最多的水。

示例:
输入: height = [1,8,6,2,5,4,8,3,7]
输出: 49
解释: max(min(8,7) * 8) = 49

思路分析:

容器的面积 = min(左边高度, 右边高度) × 宽度

暴力解法是枚举所有可能的两条线:

maxArea := 0
for i := 0; i < n; i++ {
    for j := i+1; j < n; j++ {
        area := min(height[i], height[j]) * (j - i)
        maxArea = max(maxArea, area)
    }
}
// O(n²)

双指针优化的关键:

  • 初始时,宽度最大(left=0, right=n-1)
  • 移动较短的那条线,才有可能增加面积
  • 为什么不移动较长的线?因为移动后宽度变小,而高度由较短的线决定,面积只会更小

完整代码:

func maxArea(height []int) int {
    left, right := 0, len(height)-1
    maxWater := 0

    for left < right {
        // 计算当前面积
        width := right - left
        h := min(height[left], height[right])
        area := width * h
        maxWater = max(maxWater, area)

        // 移动较短的那条线
        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }

    return maxWater
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

为什么这个贪心策略是正确的?

很多人会疑惑:移动短板一定能找到最大面积吗?

证明:假设当前 height[left] < height[right]

  1. 如果移动right,新面积 = min(height[left], height[right-1]) × (right-1-left)

    • 宽度变小了
    • 高度最多是heightleft
    • 所以新面积 ≤ 原面积

  2. 如果移动left,新面积 = min(height[left+1], height[right]) × (right-left-1)

    • 宽度变小了
    • 但高度可能变大(如果height[left+1] > height[left])
    • 有可能新面积 > 原面积

所以移动短板才有可能找到更大面积。

三、快慢指针

3.1 [LeetCode 26] 删除有序数组中的重复项

这道题看起来简单,但很多人写不出最优解。

题目:

给定有序数组,原地删除重复元素,返回新长度。
不能使用额外空间,必须原地修改。

示例:
输入: nums = [0,0,1,1,1,2,2,3,3,4]
输出: 5, nums = [0,1,2,3,4,_,_,_,_,_]

思路分析:

新手容易想到创建新数组:

result := []int{}
for i := 0; i < len(nums); i++ {
    if i == 0 || nums[i] != nums[i-1] {
        result = append(result, nums[i])
    }
}
// 空间复杂度O(n),不符合题目要求

双指针原地删除:

  • slow指针:指向不重复元素应该放的位置
  • fast指针:遍历数组
初始:
slow fast
 ↓    ↓
[0, 0, 1, 1, 1, 2, 2, 3, 3, 4]

当fast=1时,nums[fast]=0,和nums[slow]重复,fast++
当fast=2时,nums[fast]=1,不重复,slow++,nums[slow]=1

最终:
        slow
         ↓
[0, 1, 2, 3, 4, 2, 2, 3, 3, 4]
                ↑
               fast

返回slow+1 = 5

完整代码:

func removeDuplicates(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    slow := 0
    for fast := 1; fast < len(nums); fast++ {
        if nums[fast] != nums[slow] {
            slow++
            nums[slow] = nums[fast]
        }
    }

    return slow + 1
}

变种题:

  • [LeetCode 80] 删除有序数组中的重复项 II(允许重复2次)
  • [LeetCode 27] 移除元素
  • [LeetCode 283] 移动零

3.2 [LeetCode 141] 环形链表

这道题是快慢指针的经典应用,字节面试高频题。

题目:

判断链表是否有环。

示例:
1 → 2 → 3 → 4
    ↑       ↓
    ← ← ← ←
返回true

思路分析:

暴力解法:用哈希表记录访问过的节点

visited := make(map[*ListNode]bool)
for head != nil {
    if visited[head] {
        return true
    }
    visited[head] = true
    head = head.Next
}
return false
// 空间复杂度O(n)

快慢指针(Floyd判圈算法):

  • slow每次走1步
  • fast每次走2步
  • 如果有环,fast一定会追上slow

为什么fast一定能追上slow?

想象操场跑步,快的人每次多跑一圈,最终一定会套圈。

数学证明:

  • 假设环的长度为C
  • slow进入环后,fast也在环内某位置
  • 每次循环,fast和slow的距离缩小1
  • 最多C次循环,fast就会追上slow

完整代码:

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

    slow, fast := head, head

    for fast != nil && fast.Next != nil {
        slow = slow.Next        // 走1步
        fast = fast.Next.Next   // 走2步

        if slow == fast {
            return true
        }
    }

    return false
}

进阶问题:如何找到环的入口?

[LeetCode 142] 环形链表 II - 这道题在字节、美团面试中经常出现。

思路:

  1. 先用快慢指针找到相遇点
  2. 让slow从头开始,fast从相遇点开始,都每次走1步
  3. 再次相遇的点就是环的入口

数学证明:

假设:
- 头节点到环入口距离为a
- 环入口到相遇点距离为b
- 相遇点到环入口距离为c
- 环长度为 b+c

第一次相遇时:
- slow走了 a+b
- fast走了 a+b+n(b+c),n为fast在环内转的圈数

因为fast速度是slow的2倍:
2(a+b) = a+b+n(b+c)
a+b = n(b+c)
a = n(b+c) - b
a = (n-1)(b+c) + c

这意味着:从头走a步 = 从相遇点走c步再转(n-1)圈
所以从头和从相遇点同时走,会在环入口相遇

完整代码:

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

    // 1. 找到相遇点
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next

        if slow == fast {
            // 2. 找环入口
            slow = head
            for slow != fast {
                slow = slow.Next
                fast = fast.Next
            }
            return slow
        }
    }

    return nil
}

四、滑动窗口

滑动窗口是双指针的进阶应用,也是面试中最难的部分。很多人卡在这里,但理解了模板后会发现很简单。

4.1 滑动窗口模板

滑动窗口适用于求连续子数组/子串的最值问题。

核心思想:

  • 维护一个窗口 [left, right]
  • right不断右移扩大窗口
  • 当窗口不满足条件时,left右移缩小窗口

通用模板:

func slidingWindow(s string) int {
    left, right := 0, 0
    window := make(map[byte]int) // 窗口内元素的频率

    for right < len(s) {
        // 1. 扩大窗口
        c := s[right]
        right++
        window[c]++

        // 2. 判断是否需要缩小窗口
        for 窗口需要缩小的条件 {
            // 3. 缩小窗口
            d := s[left]
            left++
            window[d]--
        }

        // 4. 更新结果(根据题目要求)
    }

    return 结果
}

4.2 [LeetCode 3] 无重复字符的最长子串

这道题是滑动窗口的入门题,腾讯、字节高频。

题目:

给定字符串,找出不含重复字符的最长子串的长度。

示例:
输入: "abcabcbb"
输出: 3
解释: 最长子串是"abc"

思路分析:

暴力解法:枚举所有子串,判断是否有重复字符,O(n³)

滑动窗口:

初始: left=0, right=0, window={}

right=0, s[0]='a', window={'a':1}, len=1
right=1, s[1]='b', window={'a':1,'b':1}, len=2
right=2, s[2]='c', window={'a':1,'b':1,'c':1}, len=3
right=3, s[3]='a', window={'a':2,...}, 有重复!
    缩小窗口:left右移,移除window['a'],直到无重复

完整代码:

func lengthOfLongestSubstring(s string) int {
    window := make(map[byte]int)
    left, right := 0, 0
    maxLen := 0

    for right < len(s) {
        // 扩大窗口
        c := s[right]
        right++
        window[c]++

        // 缩小窗口:当有重复字符时
        for window[c] > 1 {
            d := s[left]
            left++
            window[d]--
        }

        // 更新结果
        maxLen = max(maxLen, right-left)
    }

    return maxLen
}

时间复杂度😮(n)

  • right指针遍历一遍:O(n)
  • left指针最多移动n次:O(n)
  • 总时间:O(2n) = O(n)

4.3 [LeetCode 76] 最小覆盖子串

这道题是滑动窗口的hard题,字节二面高频,很多人直接放弃,但用模板其实不难。

题目:

给定字符串s和t,找出s中包含t所有字符的最小子串。

示例:
输入: s = "ADOBECODEBANC", t = "ABC"
输出: "BANC"

思路分析:

关键点:

  1. 用need记录t中每个字符需要的次数
  2. 用window记录窗口内每个字符的次数
  3. valid记录窗口内满足need的字符种类数
need = {'A':1, 'B':1, 'C':1}

扩大窗口直到包含所有字符:
s = "ADOBECODEBANC"
     ↑       ↑
    left    right
window = {'A':1,'D':1,'O':2,'B':1,'E':1,'C':1}
valid = 3(A,B,C都满足)

缩小窗口寻找最小:
s = "ADOBECODEBANC"
         ↑   ↑
        left right

完整代码:

func minWindow(s string, t string) string {
    need := make(map[byte]int)
    window := make(map[byte]int)

    // 统计t中字符的频率
    for i := 0; i < len(t); i++ {
        need[t[i]]++
    }

    left, right := 0, 0
    valid := 0 // 窗口中满足need条件的字符种类数

    // 记录最小覆盖子串的起始位置和长度
    start, length := 0, len(s)+1

    for right < len(s) {
        // 扩大窗口
        c := s[right]
        right++

        if need[c] > 0 {
            window[c]++
            if window[c] == need[c] {
                valid++
            }
        }

        // 缩小窗口:当窗口包含所有字符时
        for valid == len(need) {
            // 更新最小覆盖子串
            if right-left < length {
                start = left
                length = right - left
            }

            // 缩小窗口
            d := s[left]
            left++

            if need[d] > 0 {
                if window[d] == need[d] {
                    valid--
                }
                window[d]--
            }
        }
    }

    if length == len(s)+1 {
        return ""
    }
    return s[start:start+length]
}

调试技巧:

如果你的代码wa了,试着打印这些变量:

fmt.Printf("right=%d, c=%c, window=%v, valid=%d\n", right, c, window, valid)
fmt.Printf("left=%d, d=%c, window=%v, valid=%d\n", left, d, window, valid)

五、实战技巧

5.1 如何识别双指针题型

看到这些关键词,90%是双指针:

  • "有序数组"
  • "两数之和"
  • "去重"
  • "回文"
  • "最长/最短子串"
  • "无重复"
  • "原地修改"

5.2 常见坑点

坑1:边界条件

// 错误:没有判断数组是否为空
left, right := 0, len(arr)-1
// 如果arr为空,right=-1,出错

// 正确:
if len(arr) == 0 {
    return 结果
}

坑2:死循环

// 错误:忘记移动指针
for left < right {
    if arr[left] < arr[right] {
        // 缺少 left++ 或 right--
    }
}

// 正确:每个分支都要移动指针

坑3:数组越界

// 错误:
for i > 0 && arr[i] == arr[i-1] { // i=0时会越界

// 正确:
if i > 0 && arr[i] == arr[i-1] {

5.3 时间复杂度分析

很多人以为双重循环就是O(n²),其实不一定:

left, right := 0, n-1
for left < right {
    // 每次循环,left++或right--
    // left最多移动n次,right最多移动n次
    // 总共最多2n次操作
    // 时间复杂度O(n)
}

关键:虽然是嵌套循环,但每个元素最多被访问常数次。

六、题目清单

按难度分类,建议按顺序刷:

Easy(入门必刷):

  • [LeetCode 26] 删除有序数组中的重复项
  • [LeetCode 27] 移除元素
  • [LeetCode 283] 移动零
  • [LeetCode 344] 反转字符串
  • [LeetCode 125] 验证回文串

Medium(面试高频):

  • [LeetCode 167] 两数之和 II
  • [LeetCode 15] 三数之和
  • [LeetCode 11] 盛最多水的容器
  • [LeetCode 3] 无重复字符的最长子串
  • [LeetCode 438] 找到字符串中所有字母异位词
  • [LeetCode 209] 长度最小的子数组

Hard(挑战自我):

  • [LeetCode 76] 最小覆盖子串
  • [LeetCode 42] 接雨水
  • [LeetCode 239] 滑动窗口最大值

七、面试真题

字节跳动二面(2024.03)

题目:给定数组和目标值,找出所有和为目标值的四元组。

分析:这是三数之和的扩展,用同样的思路:固定两个数,双指针找剩余两个数。

腾讯一面(2024.02)

题目:给定字符串,找出最长的回文子串。

分析:可以用双指针从中心扩展,也可以用动态规划。双指针解法更直观。