滑动窗口与双指针

#算法 · #双指针 · #滑动窗口 · #快慢指针 · #左右指针

双指针和滑动窗口是处理数组、字符串问题的利器。它们将 O(n²) 的暴力枚举优化为 O(n)，在面试中出场率极高。

双指针分类

1. 左右指针（对撞指针）

两个指针从两端向中间移动。

// 两数之和 II（有序数组）
func twoSum(numbers []int, target int) []int {
    l, r := 0, len(numbers)-1
    for l < r {
        sum := numbers[l] + numbers[r]
        if sum == target {
            return []int{l + 1, r + 1}
        } else if sum < target {
            l++
        } else {
            r--
        }
    }
    return nil
}

经典场景：

问题	技巧
两数之和（有序）	和太小左指针右移，太大右指针左移
三数之和	固定一个 + 两数之和
盛最多水的容器	移动较矮的一边
反转数组/字符串	l++, r-- 交换
验证回文串	跳过非字母数字后对撞

2. 快慢指针

一快一慢，常用于链表。

// 判断链表是否有环（Floyd 判圈）
func hasCycle(head *ListNode) bool {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false
}

// 找环的入口
func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            // 相遇后，从 head 和相遇点同时出发，相遇点即为入口
            ptr := head
            for ptr != slow {
                ptr = ptr.Next
                slow = slow.Next
            }
            return ptr
        }
    }
    return nil
}

经典场景：

问题	技巧
链表判环	快慢指针相遇
找环入口	从 head 和相遇点同时走
链表中点	快指针到末尾时慢指针在中点
删除倒数第 N 个	快指针先走 N 步
寻找重复数	快慢指针 + 环入口（Floyd）

3. 分离双指针

两个指针分别在两个数组/链表上移动。

// 合并两个有序数组
func merge(nums1 []int, m int, nums2 []int, n int) {
    p1, p2, p := m-1, n-1, m+n-1
    for p1 >= 0 && p2 >= 0 {
        if nums1[p1] > nums2[p2] {
            nums1[p] = nums1[p1]
            p1--
        } else {
            nums1[p] = nums2[p2]
            p2--
        }
        p--
    }
    for p2 >= 0 {
        nums1[p] = nums2[p2]
        p--
        p2--
    }
}

滑动窗口

核心框架

// 滑动窗口通用模板
func slidingWindow(s string) {
    window := make(map[byte]int) // 窗口内数据
    left, right := 0, 0

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

        // 2. 更新窗口数据（根据题目需要）

        // 3. 缩小窗口（当窗口不满足条件时）
        for needShrink() {
            d := s[left]
            left++
            window[d]--
            // 更新窗口数据
        }
    }
}

经典问题

最小覆盖子串

// s 中覆盖 t 所有字符的最小子串
func minWindow(s, t string) string {
    need := make(map[byte]int)
    for i := range t {
        need[t[i]]++
    }

    window := make(map[byte]int)
    left, right := 0, 0
    valid := 0  // 已满足的字符种类数
    start, minLen := 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 < minLen {
                start = left
                minLen = right - left
            }

            d := s[left]
            left++
            if need[d] > 0 {
                if window[d] == need[d] {
                    valid--
                }
                window[d]--
            }
        }
    }

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

无重复字符的最长子串

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]--
        }

        if right-left > maxLen {
            maxLen = right - left
        }
    }
    return maxLen
}

滑动窗口适用条件

问题满足以下特征 → 滑动窗口：
1. 求子数组/子串
2. 满足某种条件的"最长"或"最短"
3. 窗口扩大时条件单调变化
   （如窗口越大，和越大 → 单调性）

变体

变体	场景	例题
固定窗口	窗口大小固定	大小为 K 的子数组最大平均值
可变窗口	窗口大小动态变化	最小覆盖子串
计数窗口	窗口内统计	恰好包含 K 个不同字符的最长子串
条件窗口	满足某种条件	和 ≥ target 的最短子数组
多指针窗口	两个 left	至多包含两个不同字符的最长子串

单调队列：滑动窗口最大值

问题

给定数组 nums 和窗口大小 k，求每个窗口内的最大值。

单调队列原理

维护一个双端队列，队列内元素单调递减。队首永远是当前窗口的最大值。

入队规则：新元素 x 加入时，
  从队尾弹出所有 < x 的元素（它们不可能是未来的最大值）
  → 保持队列递减

出队规则：窗口滑动时，
  如果队首索引 < 窗口左边界，弹出

Go 实现

func maxSlidingWindow(nums []int, k int) []int {
    res := make([]int, 0, len(nums)-k+1)
    deque := make([]int, 0) // 存索引，保证 O(1) 判断过期

    for i, v := range nums {
        // 1. 入队：弹出队尾所有 < v 的索引
        for len(deque) > 0 && nums[deque[len(deque)-1]] < v {
            deque = deque[:len(deque)-1]
        }
        deque = append(deque, i)

        // 2. 出队：队首过期（窗口左边界外）
        if deque[0] < i-k+1 {
            deque = deque[1:]
        }

        // 3. 记录结果：窗口形成后（i >= k-1）
        if i >= k-1 {
            res = append(res, nums[deque[0]])
        }
    }
    return res
}

单调队列 vs 堆

维度	单调队列	堆（优先队列）
滑动窗口最大值	O(n)	O(n log k)
元素删除	O(1) 从两端	O(log n) 需要 lazy deletion
顺序要求	必须在线性序列上滑动	不要求

单调队列扩展

// 通用模板：维护滑动窗口内的最值
type MonotonicQueue struct {
    data []int
}

// Push: 入队，保持单调性
func (mq *MonotonicQueue) Push(x int) {
    for len(mq.data) > 0 && mq.data[len(mq.data)-1] < x {
        mq.data = mq.data[:len(mq.data)-1]
    }
    mq.data = append(mq.data, x)
}

// Pop: 出队左侧指定元素
func (mq *MonotonicQueue) Pop(x int) {
    if len(mq.data) > 0 && mq.data[0] == x {
        mq.data = mq.data[1:]
    }
}

// Max: 获取最大值（单调递减队列的队首）
func (mq *MonotonicQueue) Max() int {
    return mq.data[0]
}

面试高频题

双指针

三数之和 — 排序 + 固定 + 对撞指针
盛最多水的容器 — 对撞指针 + 贪心
接雨水 — 左右各维护最大高度
环形链表 II — 快慢指针 + 数学推导

滑动窗口

无重复字符的最长子串 — 窗口 + hashset
最小覆盖子串 — 窗口 + 计数
找到字符串中所有字母异位词 — 固定窗口 + 计数
滑动窗口最大值 — 单调队列

复杂度对比

问题	暴力	双指针/滑动窗口
三数之和	O(n³)	O(n²)
最小覆盖子串	O(n²·m)	O(n+m)
盛最多水容器	O(n²)	O(n)
无重复最长子串	O(n²)	O(n)

Hard 题完整代码

最小覆盖子串（Minimum Window Substring）

func minWindow(s string, t string) string {
    need := make(map[byte]int)
    for i := 0; i < len(t); i++ { need[t[i]]++ }

    window := make(map[byte]int)
    left, right := 0, 0
    valid := 0 // 窗口内已满足的字符种类数
    start, minLen := 0, math.MaxInt32

    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 < minLen {
                start = left
                minLen = right - left
            }
            d := s[left]
            left++
            if need[d] > 0 {
                if window[d] == need[d] { valid-- }
                window[d]--
            }
        }
    }
    if minLen == math.MaxInt32 { return "" }
    return s[start : start+minLen]
}

mermaid

flowchart TB
    subgraph Window["滑动窗口动画 — s='ADOBECODEBANC', t='ABC'"]
        direction TB
        S1["[A]DOBECODEBANC<br/>window: {A:1}, valid=1/3"]
        S2["[AD]OBECODEBANC<br/>window: {A:1, D:1}, valid=1/3"]
        S3["[ADO]BECODEBANC<br/>window: {A:1, D:1, O:1}, valid=1/3"]
        S4["[ADOB]ECODEBANC<br/>window: {A:1, B:1, ...}, valid=2/3"]
        S5["[ADOBE]CODEBANC<br/>window: {A:1, B:1, E:1}, valid=2/3"]
        S6["[ADOBEC]ODEBANC<br/>window: {A:1, B:1, C:1}, valid=3/3 ✅<br/>→ 但太大，开始缩左"]
        S7["A[DOBEC]ODEBANC<br/>去掉A后 valid=2/3 → 停止缩小"]
        S8["... 继续扩大 → [CODEBA]NC<br/>valid=3/3, len=6 ✅<br/>继续缩 → ODEBA[N]C<br/>发现更短 → [BANC] len=4 ✅"]
    end

    S1 --> S2 --> S3 --> S4 --> S5 --> S6 --> S7 --> S8
    style S6 fill:#4CAF50,color:#fff
    style S8 fill:#4CAF50,color:#fff

找到字符串中所有字母异位词

func findAnagrams(s string, p string) []int {
    need := make(map[byte]int)
    for i := 0; i < len(p); i++ { need[p[i]]++ }

    window := make(map[byte]int)
    left, right := 0, 0
    valid := 0
    var res []int

    for right < len(s) {
        c := s[right]
        right++
        if need[c] > 0 {
            window[c]++
            if window[c] == need[c] { valid++ }
        }

        // 窗口大小固定为 len(p) → 收缩
        for right-left >= len(p) {
            if valid == len(need) {
                res = append(res, left)
            }
            d := s[left]
            left++
            if need[d] > 0 {
                if window[d] == need[d] { valid-- }
                window[d]--
            }
        }
    }
    return res
}

// 示例: s="cbaebabacd", p="abc"
// 输出: [0, 6]
// 解释: "cba" 和 "bac" 是 "abc" 的异位词

字符串的排列（Permutation in String）

func checkInclusion(s1 string, s2 string) bool {
    need := make(map[byte]int)
    for i := 0; i < len(s1); i++ { need[s1[i]]++ }

    window := make(map[byte]int)
    left, right := 0, 0
    valid := 0

    for right < len(s2) {
        c := s2[right]
        right++
        if need[c] > 0 {
            window[c]++
            if window[c] == need[c] { valid++ }
        }

        // 窗口固定大小 = len(s1)
        for right-left >= len(s1) {
            if valid == len(need) { return true }
            d := s2[left]
            left++
            if need[d] > 0 {
                if window[d] == need[d] { valid-- }
                window[d]--
            }
        }
    }
    return false
}

无重复字符的最长子串

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

    for right < len(s) {
        c := s[right]
        right++
        window[c]++

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

        if right-left > maxLen {
            maxLen = right - left
        }
    }
    return maxLen
}

滑动窗口最大值（Sliding Window Maximum）

func maxSlidingWindow(nums []int, k int) []int {
    var res []int
    // 单调递减队列，存的是索引（不是值）
    deque := make([]int, 0)

    for i, v := range nums {
        // 1. 队列头超出窗口 → 移除
        if len(deque) > 0 && deque[0] <= i-k {
            deque = deque[1:]
        }
        // 2. 维护单调递减：弹出队尾小于当前值的元素
        for len(deque) > 0 && nums[deque[len(deque)-1]] < v {
            deque = deque[:len(deque)-1]
        }
        // 3. 当前元素入队
        deque = append(deque, i)
        // 4. 窗口形成后，队头就是最大值
        if i >= k-1 {
            res = append(res, nums[deque[0]])
        }
    }
    return res
}

mermaid

flowchart TB
    subgraph Deque["单调队列演示 — nums=[1,3,-1,-3,5,3,6,7], k=3"]
        direction LR
        D1["i=0, val=1<br/>queue: [1]"]
        D2["i=1, val=3<br/>3>1 → pop 1<br/>queue: [3]"]
        D3["i=2, val=-1<br/>-1<3 → 直接加<br/>queue: [3,-1]<br/>max=3 ✅"]
        D4["i=3, val=-3<br/>queue: [3,-1,-3]<br/>pop 3(出窗口)<br/>queue: [-1,-3]<br/>max=-1"]
        D5["i=4, val=5<br/>5 > all → pop all<br/>queue: [5]<br/>max=5"]
    end

    D1 --> D2 --> D3 --> D4 --> D5
    style D1 fill:#f44336,color:#fff
    style D2 fill:#f44336,color:#fff
    style D3 fill:#4CAF50,color:#fff
    style D4 fill:#FF9800,color:#fff
    style D5 fill:#4CAF50,color:#fff

滑动窗口通用框架

// 适用于 90% 滑动窗口题目的通用模板
func slidingWindow(s string) {
    need := make(map[byte]int)   // 目标字符计数
    window := make(map[byte]int) // 窗口内字符计数
    left, right := 0, 0
    valid := 0 // 满足条件的字符种类数

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

        // 2. 判断是否需要缩小窗口
        for /* 窗口需要缩小的条件 */ {
            // 3. 缩小窗口前的操作（记录结果等）
            d := s[left]
            left++
            // ... 更新窗口数据 ...
        }
    }
}

题目变种	窗口条件	收缩条件
最小覆盖子串	所有字符数量达标	`valid == len(need)`
字母异位词	窗口大小固定	`right-left >= len(p)`
无重复最长子串	不能有重复	`window[c] > 1`
滑动窗口最大值	窗口大小固定	用单调队列维护

滑动窗口与双指针 ​

双指针分类 ​

1. 左右指针（对撞指针） ​

2. 快慢指针 ​

3. 分离双指针 ​

滑动窗口 ​

核心框架 ​

经典问题 ​

最小覆盖子串 ​

无重复字符的最长子串 ​

滑动窗口适用条件 ​

变体 ​

单调队列：滑动窗口最大值 ​

问题 ​

单调队列原理 ​

Go 实现 ​

单调队列 vs 堆 ​

单调队列扩展 ​

面试高频题 ​

双指针 ​

滑动窗口 ​

复杂度对比 ​

Hard 题完整代码 ​

最小覆盖子串（Minimum Window Substring） ​

找到字符串中所有字母异位词 ​

字符串的排列（Permutation in String） ​

无重复字符的最长子串 ​

滑动窗口最大值（Sliding Window Maximum） ​

滑动窗口通用框架 ​

复杂度对比 ​

💬 文章评论

滑动窗口与双指针

双指针分类

1. 左右指针（对撞指针）

2. 快慢指针

3. 分离双指针

滑动窗口

核心框架

经典问题

最小覆盖子串

无重复字符的最长子串

滑动窗口适用条件

变体

单调队列：滑动窗口最大值

问题

单调队列原理

Go 实现

单调队列 vs 堆

单调队列扩展

面试高频题

双指针

滑动窗口

复杂度对比

Hard 题完整代码

最小覆盖子串（Minimum Window Substring）

找到字符串中所有字母异位词

字符串的排列（Permutation in String）

无重复字符的最长子串

滑动窗口最大值（Sliding Window Maximum）

滑动窗口通用框架

复杂度对比