LeetCode75学习计划-滑动窗口

算法解题思路很多会借鉴于题解区，如果侵权请联系删除。

本章节知识点为滑动窗口。

子数组最大平均数 I

题目标签：

• 数组
• 滑动窗口

题目难度： Easy

题目描述：

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。

请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。

任何误差小于 10-5 的答案都将被视为正确答案。

示例：

输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75

解题思路：

• 题目要求长度为 k 的连续子数组，我们只要维护一个长度为 k 的滑动窗口去计算即可

代码实现：

func findMaxAverage(nums []int, k int) float64 {
  // 我们来维护一个最大的子数组的和，而不是直接维护平均值
  // 这样只需要在最后进行一次计算即可
  sum := 0
  for _, v := range nums[:k] {
    sum += v
  }
  maxSum := sum
  for i := k; i < len(nums); i++ {
    // 减去第一个数再加上当前的数就是当前的滑动窗口的和
    sum = sum - nums[i-k] + nums[i]
    maxSum = max(maxSum, sum)
  }
  // 返回平均数
  return float64(maxSum) / float64(k)
}

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

定长子串中元音的最大数目

题目标签：

• 字符串
• 滑动窗口

题目难度：Medium

题目描述：

给你字符串 s 和整数 k 。

请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

英文中的 元音字母 为（a, e, i, o, u）。

解题思路：

• 与上一个题目的思路一致，定长的窗口计算数量即可

代码实现：

func maxVowels(s string, k int) int {
  // count统计每一个窗口的元音数量
  count := 0
  for i := 0; i < k; i ++ {
    if isVowel(s[i]) {
      count ++
    } 
  }
  // ans 作为结果
  ans := count
  for i := k; i < len(s); i ++ {
    // 统计下一个窗口的元音数量并更新最大的元音数量
    if (isVowel(s[i-k])) {
      count --
    }
    if (isVowel(s[i])) {
      count ++
    }
    ans = max(ans, count)
  }
  return ans
}
func isVowel(s byte) bool {
  return s == 'a' || s == 'e' || s == 'i' || s == 'o' || s == 'u'
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

最大连续 1 的个数 III

题目标签：

• 数组
• 滑动窗口
• 二分查找
• 前缀和

题目难度：Medium

题目描述：

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

示例：

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

解题思路：

• 题目要求的是求反转最多k 个0得到的仅包含1的最长子数组，换言之，就是找一个最长子数组内最多允许有k个0。
• 两个指针指向滑动窗口的左右边界，右指针主动右移，如果右指针指向了 0 说明滑动窗口内增加了一个 0, 判断窗口内0 的个数，如果超过了 k， 则左指针要被迫右移，直接窗口内 0 的个数小于等于 k 才行。
• 在这个求滑动窗口的过程中，滑动窗口长度的最大值就是我们要求的值

代码实现：

func longestOnes(nums []int, k int) int {
  n := len(nums)
  // 滑动窗口的最大长度
  res := 0
  // 指针
  left, right := 0, 0
  // 0的数量
  zeros := 0
  // 主动移动右指针
  for right < n {
    if nums[right] == 0 {
      zeros ++
    }
    // 如果0的数量大于k，则移动左指针
    for zeros > k {
      if nums[left] == 0 {
        zeros --
      }
      left ++
    }
    // 更新窗口的最大值
    res = max(res, right - left + 1)
    // 更新右指针
    right ++
  }
  return res
}

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

删掉一个元素以后全为 1 的最长子数组

题目标签：

• 数组
• 滑动窗口

题目难度：Medium

题目描述：

给你一个二进制数组 nums ，你需要从中删掉一个元素。

请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。

如果不存在这样的子数组，请返回 0 。

示例：

输入：nums = [1,1,0,1]
输出：3
解释：删掉位置 2 的数后，[1,1,1] 包含 3 个 1 。

解题思路：

• 本题与上一题可以说是一样的题目，只是上题的 k 固定为1了，还有本题是删除而不是替换

代码实现：

func longestSubarray(nums []int) int {
  n := len(nums)
  // 滑动窗口的最大长度
  res := 0
  // 指针
  left, right := 0, 0
  // 0的数量
  zeros := 0
  // 主动移动右指针
  for right < n {
    if nums[right] == 0 {
      zeros ++
    }
    // 如果0的数量大于1，则移动左指针
    for zeros > 1 {
      if nums[left] == 0 {
        zeros --
      }
      left ++
    }
    // 更新窗口的最大值
    res = max(res, right - left + 1)
    // 更新右指针
    right ++
  }
  // 必须删掉一个元素
  return res - 1
}

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