滑动窗口系列

2021-03-10

字数统计: 851字 | 阅读时长: 3分

阅读量

滑动窗口使用场景：一般需要遍历整个数组/字符串，找出符合条件的子集。

滑动窗口使用方法：如下图。我们需要2个下标来标记窗口的边界值，决定窗口的大小。因为要找到符合条件的最值，所以每一次窗口滑动都需要记录一下符合要求的值，直到滑到末端，我们取其中符合条件的最值。

举个栗子：

一、题目描述

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是子串的长度，”pwke” 是一个子序列，不是子串。

二、思路分析

根据介绍的滑动窗口，我们应用到本题中

滑动窗口的边界值：x, j

if 出现重复字符

窗口左边界向右移动

计算此时的最值

else

窗口右边界向右移动

计算此时的最值

三、AC代码

func lengthOfLongestSubstring(s string) int {
    // 边界值
	if s == " " {
		return 1
	}
	lenStr := len(s)
	var maxLen int // 最大长度值
	var x, j int  // 滑动窗口的边界值
	for j < lenStr { // 判断滑动窗口是否已经到边界
		if strings.Contains(s[x:j], string(s[j])) {  // 有重复字符出现
			x = x + 1  // 窗口左边界向右移动一个单位
			if len(s[x:j+1]) > maxLen {  // 此时计算最值
				maxLen = len(s[x : j+1])
			}
		} else {
			j++ // 窗口右边界扩大
			if len(s[x:j]) > maxLen {
				maxLen = len(s[x:j]) // 此时计算最值
			}
		}
	}
	return maxLen
}

四、总结

滑动窗口原理很容易理解，主要难点在于对于给定条件，怎么找出最优值。我们可以再练练手

同系列题目：

LeetCode209.长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

AC代码：

func minSubArrayLen(target int, nums []int) int {
	lenNums := len(nums)
	var i, j, ans, minCnt int
	minCnt = lenNums + 1
	for j < lenNums {
		ans = nums[j] + ans
		if ans >= target {
			if j-i+1 < minCnt {
				minCnt = j - i + 1
			}
			ans = 0
			i++
			j = i - 1
		}
		j++
	}
	if minCnt == lenNums+1 {
		minCnt = 0
	}
	return minCnt
}

LeetCode159. 至多包含两个不同字符的最长子串

输入：s = “abccbca”

输出：5

// 滑动窗口 使用map标记哪个字符被遍历到
func ContainsTweChar(s string) int {
	var charMap map[string]int
	charMap = make(map[string]int)
	var lenS = len(s)
	var i, j int
	j++
	var maxCnt int
	for j < lenS {
		charMap[s[i:i+1]] = i
		if strings.Contains(s[i:j+1], string(s[j])) {
			charMap[s[j:j+1]] = j
		}
		if len(charMap) > 2 {
			delete(charMap, s[i:i+1])
			i++
		}
		j++
		if maxCnt < len(s[i:j]) {
			maxCnt = len(s[i:j])
		}
	}
	return maxCnt
}