滑动窗口与双指针算法

滑动窗口和双指针是解决数组/字符串问题的常用技巧，它们通过维护一个窗口或两个指针来高效地解决问题，避免暴力解法的时间复杂度。

---

滑动窗口（Sliding Window）

基本概念

滑动窗口是一种在数组或字符串上维护一个窗口的技术，通过移动窗口的左右边界来解决问题。滑动窗口主要分为两种类型：

1. 固定窗口：窗口大小固定不变
2. 可变窗口：窗口大小根据条件动态变化

核心思想

• 使用两个指针（left 和 right）表示窗口的左右边界
• 通过移动右指针扩展窗口，移动左指针收缩窗口
• 在窗口移动过程中维护窗口的状态（如和、最大值、字符计数等）

固定窗口

窗口大小固定为 k，每次移动一个位置。

算法模板

func fixedWindow(nums []int, k int) {
    n := len(nums)
    if n < k {
        return
    }
    
    // 初始化窗口 [0, k-1]
    windowSum := 0
    for i := 0; i < k; i++ {
        windowSum += nums[i]
    }
    
    // 滑动窗口
    for i := k; i < n; i++ {
        // 处理当前窗口
        // ...
        
        // 移动窗口：移除左边界，添加右边界
        windowSum = windowSum - nums[i-k] + nums[i]
    }
}

示例：滑动窗口最大值

package main

import "fmt"

// LeetCode 239. 滑动窗口最大值
func maxSlidingWindow(nums []int, k int) []int {
    n := len(nums)
    if n == 0 || k == 0 {
        return []int{}
    }
    
    result := make([]int, 0, n-k+1)
    
    // 使用双端队列存储索引，保持队列中元素单调递减
    deque := make([]int, 0)
    
    for i := 0; i < n; i++ {
        // 移除窗口外的元素
        for len(deque) > 0 && deque[0] <= i-k {
            deque = deque[1:]
        }
        
        // 移除小于当前元素的元素，保持单调递减
        for len(deque) > 0 && nums[deque[len(deque)-1]] < nums[i] {
            deque = deque[:len(deque)-1]
        }
        
        deque = append(deque, i)
        
        // 窗口形成后，记录最大值
        if i >= k-1 {
            result = append(result, nums[deque[0]])
        }
    }
    
    return result
}

// 固定窗口：计算大小为k的窗口的平均值
func averageOfSubarrays(nums []int, k int) []float64 {
    n := len(nums)
    if n < k {
        return []float64{}
    }
    
    result := make([]float64, 0, n-k+1)
    windowSum := 0
    
    // 初始化第一个窗口
    for i := 0; i < k; i++ {
        windowSum += nums[i]
    }
    result = append(result, float64(windowSum)/float64(k))
    
    // 滑动窗口
    for i := k; i < n; i++ {
        windowSum = windowSum - nums[i-k] + nums[i]
        result = append(result, float64(windowSum)/float64(k))
    }
    
    return result
}

func main() {
    nums := []int{1, 3, -1, -3, 5, 3, 6, 7}
    k := 3
    
    fmt.Println("滑动窗口最大值:", maxSlidingWindow(nums, k))
    fmt.Println("滑动窗口平均值:", averageOfSubarrays(nums, k))
    
    // 输出:
    // 滑动窗口最大值: [3 3 5 5 6 7]
    // 滑动窗口平均值: [1 1.66667 0.333333 1.66667 3.66667 5.33333]
}

可变窗口

窗口大小根据条件动态变化，通常用于找满足条件的子数组/子字符串。

算法模板

func variableWindow(nums []int) {
    left := 0
    window := make(map[int]int) // 或使用其他数据结构维护窗口状态
    
    for right := 0; right < len(nums); right++ {
        // 扩展窗口：添加 nums[right]
        window[nums[right]]++
        
        // 收缩窗口：当窗口不满足条件时
        while (窗口不满足条件) {
            // 移除 nums[left]
            window[nums[left]]--
            if window[nums[left]] == 0 {
                delete(window, nums[left])
            }
            left++
        }
        
        // 更新结果
        // ...
    }
}

示例：无重复字符的最长子串

// LeetCode 3. 无重复字符的最长子串
func lengthOfLongestSubstring(s string) int {
    if len(s) == 0 {
        return 0
    }
    
    left := 0
    maxLen := 0
    charMap := make(map[byte]int)
    
    for right := 0; right < len(s); right++ {
        // 扩展窗口
        charMap[s[right]]++
        
        // 收缩窗口：当窗口中有重复字符时
        for charMap[s[right]] > 1 {
            charMap[s[left]]--
            if charMap[s[left]] == 0 {
                delete(charMap, s[left])
            }
            left++
        }
        
        // 更新最大长度
        if right-left+1 > maxLen {
            maxLen = right - left + 1
        }
    }
    
    return maxLen
}

// LeetCode 209. 长度最小的子数组
func minSubArrayLen(target int, nums []int) int {
    left := 0
    sum := 0
    minLen := len(nums) + 1
    
    for right := 0; right < len(nums); right++ {
        // 扩展窗口
        sum += nums[right]
        
        // 收缩窗口：当窗口和 >= target 时
        for sum >= target {
            // 更新最小长度
            if right-left+1 < minLen {
                minLen = right - left + 1
            }
            // 收缩左边界
            sum -= nums[left]
            left++
        }
    }
    
    if minLen > len(nums) {
        return 0
    }
    return minLen
}

// LeetCode 76. 最小覆盖子串
func minWindow(s string, t string) string {
    if len(s) < len(t) {
        return ""
    }
    
    // 统计 t 中每个字符的出现次数
    need := make(map[byte]int)
    for i := 0; i < len(t); i++ {
        need[t[i]]++
    }
    
    left := 0
    valid := 0 // 窗口中满足条件的字符数量
    window := make(map[byte]int)
    start, minLen := 0, len(s)+1
    
    for right := 0; right < len(s); right++ {
        c := s[right]
        
        // 扩展窗口
        if need[c] > 0 {
            window[c]++
            if window[c] == need[c] {
                valid++
            }
        }
        
        // 收缩窗口：当窗口包含 t 的所有字符时
        for valid == len(need) {
            // 更新最小窗口
            if right-left+1 < minLen {
                start = left
                minLen = right - left + 1
            }
            
            // 收缩左边界
            d := s[left]
            left++
            if need[d] > 0 {
                if window[d] == need[d] {
                    valid--
                }
                window[d]--
            }
        }
    }
    
    if minLen > len(s) {
        return ""
    }
    return s[start : start+minLen]
}

---

双指针（Two Pointers）

双指针技术使用两个指针在数组或字符串中协同工作，通常用于优化暴力解法。

快慢指针

快慢指针是双指针的一种，两个指针以不同的速度移动。

应用场景

1. 检测链表中的环：Floyd 判圈算法
2. 找链表的中间节点
3. 删除链表的倒数第 N 个节点
4. 数组去重

示例代码

package main

import "fmt"

// LeetCode 141. 环形链表
type ListNode struct {
    Val  int
    Next *ListNode
}

func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }
    
    slow, fast := head, head.Next
    
    for fast != nil && fast.Next != nil {
        if slow == fast {
            return true
        }
        slow = slow.Next
        fast = fast.Next.Next
    }
    
    return false
}

// LeetCode 142. 环形链表 II - 找环的入口
func detectCycle(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return nil
    }
    
    slow, fast := head, head
    
    // 第一步：判断是否有环
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            break
        }
    }
    
    if fast == nil || fast.Next == nil {
        return nil // 无环
    }
    
    // 第二步：找环的入口
    slow = head
    for slow != fast {
        slow = slow.Next
        fast = fast.Next
    }
    
    return slow
}

// LeetCode 876. 链表的中间结点
func middleNode(head *ListNode) *ListNode {
    slow, fast := head, head
    
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    
    return slow
}

// LeetCode 19. 删除链表的倒数第 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
    }
    
    // 删除倒数第 n 个节点
    slow.Next = slow.Next.Next
    
    return dummy.Next
}

// LeetCode 26. 删除有序数组中的重复项
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
}

func main() {
    // 数组去重示例
    nums := []int{0, 0, 1, 1, 1, 2, 2, 3, 3, 4}
    length := removeDuplicates(nums)
    fmt.Println("去重后长度:", length)
    fmt.Println("去重后数组:", nums[:length])
    
    // 输出:
    // 去重后长度: 5
    // 去重后数组: [0 1 2 3 4]
}

左右指针

左右指针从数组的两端向中间移动，通常用于有序数组或字符串。

应用场景

1. 二分查找
2. 两数之和（有序数组）
3. 反转数组/字符串
4. 回文串判断
5. 盛最多水的容器

示例代码

package main

import (
    "fmt"
    "sort"
)

// LeetCode 167. 两数之和 II - 输入有序数组
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{}
}

// LeetCode 344. 反转字符串
func reverseString(s []byte) {
    left, right := 0, len(s)-1
    
    for left < right {
        s[left], s[right] = s[right], s[left]
        left++
        right--
    }
}

// LeetCode 125. 验证回文串
func isPalindrome(s string) bool {
    left, right := 0, len(s)-1
    
    for left < right {
        // 跳过非字母数字字符
        for left < right && !isAlphanumeric(s[left]) {
            left++
        }
        for left < right && !isAlphanumeric(s[right]) {
            right--
        }
        
        if toLower(s[left]) != toLower(s[right]) {
            return false
        }
        
        left++
        right--
    }
    
    return true
}

func isAlphanumeric(c byte) bool {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')
}

func toLower(c byte) byte {
    if c >= 'A' && c <= 'Z' {
        return c + 32
    }
    return c
}

// LeetCode 11. 盛最多水的容器
func maxArea(height []int) int {
    left, right := 0, len(height)-1
    maxArea := 0
    
    for left < right {
        // 计算当前面积
        width := right - left
        h := height[left]
        if height[right] < h {
            h = height[right]
        }
        area := width * h
        
        if area > maxArea {
            maxArea = area
        }
        
        // 移动较小的指针
        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }
    
    return maxArea
}

// LeetCode 15. 三数之和
func threeSum(nums []int) [][]int {
    n := len(nums)
    if n < 3 {
        return [][]int{}
    }
    
    sort.Ints(nums)
    result := make([][]int, 0)
    
    for i := 0; i < n-2; i++ {
        // 跳过重复元素
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        
        left, right := i+1, n-1
        target := -nums[i]
        
        for left < right {
            sum := nums[left] + nums[right]
            if sum == target {
                result = append(result, []int{nums[i], nums[left], nums[right]})
                
                // 跳过重复元素
                for left < right && nums[left] == nums[left+1] {
                    left++
                }
                for left < right && nums[right] == nums[right-1] {
                    right--
                }
                
                left++
                right--
            } else if sum < target {
                left++
            } else {
                right--
            }
        }
    }
    
    return result
}

func main() {
    // 两数之和示例
    numbers := []int{2, 7, 11, 15}
    target := 9
    fmt.Println("两数之和:", twoSum(numbers, target))
    
    // 三数之和示例
    nums := []int{-1, 0, 1, 2, -1, -4}
    fmt.Println("三数之和:", threeSum(nums))
    
    // 盛水容器示例
    height := []int{1, 8, 6, 2, 5, 4, 8, 3, 7}
    fmt.Println("最大面积:", maxArea(height))
    
    // 输出:
    // 两数之和: [1 2]
    // 三数之和: [[-1 -1 2] [-1 0 1]]
    // 最大面积: 49
}

---

算法对比与选择

滑动窗口 vs 双指针

特性	滑动窗口	双指针
适用场景	子数组/子字符串问题	有序数组、链表问题
窗口性质	通常维护连续区间	可以是任意两个位置
移动方式	左右边界协同移动	根据条件独立移动
典型问题	最长无重复子串、最小覆盖子串	两数之和、反转数组

选择建议

• 使用滑动窗口：

  • 需要找满足条件的连续子数组/子字符串
  • 需要维护窗口内的状态（如字符计数、和等）
  • 问题涉及”最长”、”最短”、”包含”等关键词

• 使用快慢指针：

  • 链表相关问题（环检测、找中点）
  • 数组去重、移动零等问题

• 使用左右指针：

  • 有序数组的查找问题
  • 需要从两端向中间移动的问题
  • 回文串、反转等问题

---

时间复杂度分析

• 滑动窗口：O(n)，每个元素最多被访问两次（左指针和右指针各一次）
• 双指针：O(n)，两个指针总共遍历数组一次

---

总结

滑动窗口和双指针是解决数组/字符串问题的高效技巧：

1. 滑动窗口适合处理连续子区间问题，通过维护窗口状态来优化
2. 快慢指针适合处理链表和数组的特定位置问题
3. 左右指针适合处理有序数组的查找和比较问题

掌握这些技巧可以显著提高解题效率，避免暴力解法的 O(n²) 或更高时间复杂度。

---

参考文献

• LeetCode 滑动窗口专题
• LeetCode 双指针专题
• 《算法导论》
• 《数据结构与算法分析》