基础数据结构leetcode滑动窗口专题

简介: 基础数据结构leetcode滑动窗口专题

思想

  1. 右指针右移之后窗口数据更新
  2. 判断窗口是否要收缩
  3. 左指针右移之后窗口数据更新
  4. 根据题意计算结果

模板

func minWindow(s string, t string) string {
  wind := make(map[byte]int)
  need := make(map[byte]int)
  for i := range t {
    need[t[i]]++
  }
  left, right, match, start, end, min := 0, 0, 0, 0, 0, math.MaxInt32
  for right < len(s) {
    //右移窗口
    c := s[right]
    right++
    //进行窗口内数据的一系列更新
    if need[c] != 0 {
      wind[c]++
      if wind[c] == need[c] {
        match++
      }
    }
    //判断左侧窗口是否要收缩
    for match == len(need) {
      //根据题意计算结果
      if right-left < min {
        min = right - left
        start = left
        end = right
      }
      // 左指针右移窗口
      c = s[left]
      left++
      //进行窗口内数据的一系列更新
      if need[c] != 0 {
        if wind[c] == need[c] {
          match--
        }
        wind[c]--
      }
    }
  }
  if min == math.MaxInt32 {
    return ""
  }
  return s[start:end]
}
目录
相关文章
|
1月前
【LeetCode 26】239.滑动窗口最大值
【LeetCode 26】239.滑动窗口最大值
32 1
|
1月前
【LeetCode 04】滑动窗口法总结
【LeetCode 04】滑动窗口法总结
17 0
|
3月前
|
存储 Python
【Leetcode刷题Python】239. 滑动窗口最大值
文章介绍了两种解决LeetCode上"滑动窗口最大值"问题的方法:使用大堆树和双向递减队列,提供了详细的解析和Python代码实现。
31 0
|
5月前
|
算法 搜索推荐
力扣每日一题 6/15 滑动窗口
力扣每日一题 6/15 滑动窗口
31 1
|
5月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
5月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
5月前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
5月前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
4月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
5月前
|
算法 索引
力扣随机一题 位运算/滑动窗口/数组
力扣随机一题 位运算/滑动窗口/数组
42 0