谷涧月的学习流水账

滑动窗口算法及应用场景

滑动窗口基本思想

滑动窗口主要应用在链表，数组等一维数据结构中，所谓窗口在算法中实际使用双指针来实现，主要要确定滑动指针的边界。

滑动窗口算法实例

  1. 获取链表倒数第K个节点
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    func getKthFromEnd(head *LinkNode,k int)*LinkNode{
       slow:=head
       fast:=head
       for i:=0;i<k&&fast!=nil;i++{
         fast = fast.Next
       }
       if fast==nil{
         return nil
       }
       for fast!=nil{
          slow = slow.Next
          fast.Next = fast.Next
       }
       return slow 
    }
  2. 给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    func lengthOfLongestSubstring(s string) int {
        n := len(s)
        maxLength := 0
        lastIndex := make([]int, 128)
        
        start := 0
        for fast := 0; fast < n; fast++ {
            currentChar := s[fast]
            if lastIndex[currentChar] > start {
                start = lastIndex[currentChar]
            }
            if fast-start+1 > maxLength {
                maxLength = fast - start + 1
            }
            lastIndex[currentChar] = fast + 1
        }
        
        return maxLength
    }
  3. leetcode [209] 长度最小的子数组
    给定一个含有 n 个正整数的数组和一个正整数 slow 。
    找出该数组中满足其总和大于等于 slow 的长度最小的 子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func minSubArrayLen(target int, nums []int) int {
	minLen := len(nums)+1 
	left := 0                    // 窗口的左边界
	currentSum := 0              // 当前窗口的和

	for right := 0; right < len(nums); right++ {
		currentSum += nums[right] // 将右边界的元素加入到当前窗口的和中
		// 当当前窗口的和大于等于 target 时，尝试缩小窗口
		for currentSum >= target {
			minLen = min(minLen, right-left+1) // 更新最小长度
			currentSum -= nums[left]           // 从窗口的左边界减去元素
			left++                             // 移动左边界
		}
	}

	// 如果没有找到符合条件的子数组，返回0
	if minLen == len(nums)+1  {
		return 0
	}
	return minLen
}

滑动窗口应用场景

滑动窗口算法是一种非常实用的算法技术，它在处理数组或字符串等序列数据时特别有用。以下是一些滑动窗口算法的应用场景：

  1. 寻找子数组/子串的最小/最大和：

    • 给定一个数组和一个整数k，找出所有长度为k的子数组的最大和或最小和。
    • 给定一个数组和一个目标和，找出具有最大和的连续子数组。

  2. 寻找满足条件的子数组：

    • 如前所述，寻找满足总和大于等于某个特定值的最小长度子数组。
    • 寻找数组中所有等于目标和的子数组。

  3. 字符串处理：

    • 找出字符串中不包含重复字符的最长子串。
    • 找出字符串中满足特定条件的最短子串，例如包含所有特定字符的最短子串。

  4. 数据流问题：

    • 在处理数据流时，滑动窗口可以用来维护一个固定大小的数据窗口，以便于实时计算窗口内数据的统计信息。

  5. 时间序列分析：

    • 在金融领域，滑动窗口可以用来分析特定时间段内的股票价格变动。

  6. 滑动窗口协议：

    • 在计算机网络中，滑动窗口协议用于控制数据传输，确保接收方不会因为数据量过大而处理不过来。

  7. 图像处理：

    • 在图像处理中，滑动窗口可以用来识别图像中的特定模式或特征。

  8. 机器学习特征提取：

    • 在机器学习中，滑动窗口可以用来从时间序列数据中提取特征。

  9. 游戏开发：

    • 在游戏开发中，滑动窗口可以用来检测玩家在一定时间内的行为模式。

  10. 实时监控系统：

    • 在实时监控系统中，滑动窗口可以用来检测异常行为，例如在短时间内的频繁登录尝试。

滑动窗口算法因其简单和高效而在这些场景中被广泛使用。通过维护一个动态的窗口，算法可以在不遍历整个数据集的情况下，快速找到满足特定条件的数据子集。

数据结构与算法