LeetCode Go · 滑动窗口（1）

来源与许可

题目版权归 LeetCode；题解来自 Doocs/leetcode，按 CC BY-SA 4.0 共享。补充 Go 代码来自灵茶山艾府、halfrost，保留 MIT 许可及逐题署名。本站提取 Go、调整分类及折叠排版；标注“本站整理”的 Go 解法依据题意与参考思路补写，按 CC BY-SA 4.0 共享。收录日期：2026-10-31；主题源版本：91ef8c241a5e。

本卷 30 题 · 点击题目展开，先独立思考，再查看解法。

3. 无重复字符的最长子串

中等1 种解法

标签：哈希表、字符串、滑动窗口

题目、示例与约束

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

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

示例 3:

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

提示：

0 <= s.length <= 10⁵
s 由英文字母、数字、符号和空格组成

方法一：滑动窗口 · Go 实现

思考

若枚举所有子串再判断是否含有重复字符，时间复杂度至少为 $O (n^{2})$ 。 $n \leq 10^{5}$ ，无法通过。

子串之间大量重叠：一旦区间 $[l, r]$ 已经不含重复字符，右端再纳入字符 $c$ 时，只需处理 $c$ 是否在窗口内再次出现，而不必重新扫描整段。若出现重复，合法解不可能再包含左侧多出来的那个 $c$ ，应当右移 $l$ 。用计数表维护 $cnt [c]$ ，大于 $1$ 时收缩左端，直到 $c$ 只出现一次；此时当前窗口就是以 $r$ 结尾的最长无重复子串。

我们可以用两个指针 $l$ 和 $r$ 维护一个滑动窗口，使其始终满足窗口内没有重复字符，初始时 $l$ 和 $r$ 都指向字符串的第一个字符。用一个哈希表或者长度为 $128$ 的数组 $cnt$ 来记录每个字符出现的次数，其中 $cnt [c]$ 表示字符 $c$ 出现的次数。

接下来，我们依次移动右指针 $r$ ，每次移动时，将 $cnt [s [r]]$ 的值加 $1$ ，然后判断当前窗口 $[l, r]$ 内 $cnt [s [r]]$ 是否大于 $1$ ，如果大于 $1$ ，说明当前窗口内有重复字符，我们需要移动左指针 $l$ ，直到窗口内没有重复字符为止。然后，我们更新答案 $ans = max (ans, r - l + 1)$ 。

最终，我们返回答案 $ans$ 即可。

时间复杂度 $O (n)$ ，其中 $n$ 为字符串的长度。空间复杂度 $O (| Σ |)$ ，其中 $Σ$ 表示字符集，这里 $Σ$ 的大小为 $128$ 。

func lengthOfLongestSubstring(s string) (ans int) {
	cnt := [128]int{}
	l := 0
	for r, c := range s {
		cnt[c]++
		for cnt[c] > 1 {
			cnt[s[l]]--
			l++
		}
		ans = max(ans, r-l+1)
	}
	return
}

力扣原题 · Doocs 题解来源

30. 串联所有单词的子串

困难1 种解法

标签：哈希表、字符串、滑动窗口

题目、示例与约束

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = ["ab","cd","ef"]，那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"，和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

提示：

1 <= s.length <= 10⁴
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] 和 s 由小写英文字母组成

方法一：哈希表 + 滑动窗口 · Go 实现

思考

串联子串的长度固定为 $n \cdot k$ 。若枚举 $s$ 的每个起点再判断该窗口是否为 $w o r d s$ 的某个排列，每个窗口还需切成 $n$ 段，时间约为 $O (m n k)$ 。在 $m \leq 10^{4}$ 、 $n \leq 5000$ 、 $k \leq 30$ 的范围下无法通过。

单词等长，合法窗口的起点必然落在模 $k$ 的同一剩余类中，且相邻窗口只相差一个单词。因此词频可以用哈希表沿窗口差分维护，而不必每个起点重新统计。对齐方式只有 $k$ 种。

为此对每个余数 $i \in [0, k)$ 维护一个滑动窗口：右端每次纳入一个长为 $k$ 的词；词不在 $c n t$ 中则整窗作废；某词次数过多则收缩左端；窗口恰好含 $n$ 个词时记下左端。每个字符进出窗口常数次，总时间 $O (m k)$ 。

我们用哈希表 $c n t$ 统计 $w o r d s$ 中每个单词出现的次数，用哈希表 $c n t 1$ 统计当前滑动窗口中每个单词出现的次数。我们记字符串 $s$ 的长度为 $m$ ，字符串数组 $w o r d s$ 中单词的数量为 $n$ ，每个单词的长度为 $k$ 。

我们可以枚举滑动窗口的起点 $i$ ，其中 $0 < i < k$ 。对于每个起点，我们维护一个滑动窗口，左边界为 $l$ ，右边界为 $r$ ，滑动窗口中的单词个数为 $t$ ，另外用一个哈希表 $c n t 1$ 统计滑动窗口中每个单词出现的次数。

每一次，我们提取字符串 $s [r : r + k]$ ，如果 $s [r : r + k]$ 不在哈希表 $c n t$ 中，说明当前滑动窗口中的单词不合法，我们将左边界 $l$ 更新为 $r$ ，同时将哈希表 $c n t 1$ 清空，单词个数 $t$ 重置为 0。如果 $s [r : r + k]$ 在哈希表 $c n t$ 中，说明当前滑动窗口中的单词合法，我们将单词个数 $t$ 加 1，将哈希表 $c n t 1$ 中 $s [r : r + k]$ 的次数加 1。如果 $c n t 1 [s [r : r + k]]$ 大于 $c n t [s [r : r + k]]$ ，说明当前滑动窗口中 $s [r : r + k]$ 出现的次数过多，我们需要将左边界 $l$ 右移，直到 $c n t 1 [s [r : r + k]] = c n t [s [r : r + k]]$ 。如果 $t = n$ ，说明当前滑动窗口中的单词正好合法，我们将左边界 $l$ 加入答案数组。

时间复杂度 $O (m \times k)$ ，空间复杂度 $O (n \times k)$ 。其中 $m$ 和 $n$ 分别是字符串 $s$ 和字符串数组 $w o r d s$ 的长度，而 $k$ 是字符串数组 $w o r d s$ 中单词的长度。

func findSubstring(s string, words []string) (ans []int) {
	cnt := make(map[string]int)
	for _, w := range words {
		cnt[w]++
	}
	m, n, k := len(s), len(words), len(words[0])
	for i := 0; i < k; i++ {
		l, r := i, i
		cnt1 := make(map[string]int)
		for r+k <= m {
			t := s[r : r+k]
			r += k

			if _, exists := cnt[t]; !exists {
				cnt1 = make(map[string]int)
				l = r
				continue
			}
			cnt1[t]++
			for cnt1[t] > cnt[t] {
				w := s[l : l+k]
				cnt1[w]--
				if cnt1[w] == 0 {
					delete(cnt1, w)
				}
				l += k
			}
			if r-l == n*k {
				ans = append(ans, l)
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

76. 最小覆盖子串

困难1 种解法

标签：哈希表、字符串、滑动窗口

题目、示例与约束

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。

测试用例保证答案唯一。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

m == s.length
n == t.length
1 <= m, n <= 10⁵
s 和 t 由英文字母组成

进阶：你能设计一个在 O(m + n) 时间内解决此问题的算法吗？

方法一：计数 + 双指针 · Go 实现

思考

若枚举 $s$ 的所有子串再检查是否覆盖 $t$ ，窗口有 $O (m^{2})$ 个， $m \leq 10^{5}$ 无法通过。进阶要求 $O (m + n)$ 。

覆盖一旦成立，左端多余字符可以移出窗口；尚未覆盖则只能继续右扩。因此维护 $t$ 的字符配额 $need$ 、窗口计数 $window$ ，并用 $cnt$ 记录已经凑齐的必要出现次数，判断覆盖只需常数时间。右指针扫描 $s$ ，窗口合法时尽量收缩左端并记录最短区间。

我们用一个哈希表或数组 $need$ 统计字符串 $t$ 中每个字符出现的次数，用另一个哈希表或数组 $window$ 统计滑动窗口中每个字符出现的次数。另外，定义两个指针 $l$ 和 $r$ 分别指向窗口的左右边界，变量 $cnt$ 表示窗口中已经包含了 $t$ 中的多少个字符，变量 $k$ 和 $mi$ 分别表示最小覆盖子串的起始位置和长度。

我们从左到右遍历字符串 $s$ ，对于当前遍历到的字符 $s [r]$ ：

我们将其加入窗口中，即 $window [s [r]] = window [s [r]] + 1$ ，如果此时 $need [s [r]] \geq window [s [r]]$ ，则说明 $s [r]$ 是一个「必要的字符」，我们将 $cnt$ 加一。
如果 $cnt$ 等于 $t$ 的长度，说明此时窗口中已经包含了 $t$ 中的所有字符，我们就可以尝试更新最小覆盖子串的起始位置和长度了。如果 $r - l + 1 < mi$ ，说明当前窗口表示的子串更短，我们就更新 $mi = r - l + 1$ 和 $k = l$ 。
然后，我们尝试移动左边界 $l$ ，如果此时 $need [s [l]] \geq window [s [l]]$ ，则说明 $s [l]$ 是一个「必要的字符」，移动左边界时会把 $s [l]$ 这个字符从窗口中移除，因此我们需要将 $cnt$ 减一，然后更新 $window [s [l]] = window [s [l]] - 1$ ，并将 $l$ 右移一位。
如果 $cnt$ 与 $t$ 的长度不相等，说明此时窗口中还没有包含 $t$ 中的所有字符，我们就不需要移动左边界了，直接将 $r$ 右移一位，继续遍历即可。

遍历结束，如果没有找到最小覆盖子串，返回空字符串，否则返回 $s [k : k + mi]$ 即可。

时间复杂度 $O (m + n)$ ，空间复杂度 $O (| Σ |)$ 。其中 $m$ 和 $n$ 分别是字符串 $s$ 和 $t$ 的长度；而 $| Σ |$ 是字符集的大小，本题中 $| Σ | = 128$ 。

func minWindow(s string, t string) string {
	need := make([]int, 128)
	window := make([]int, 128)
	for i := 0; i < len(t); i++ {
		need[t[i]]++
	}

	m, n := len(s), len(t)
	k, mi, cnt := -1, m+1, 0

	for l, r := 0, 0; r < m; r++ {
		c := s[r]
		if window[c]++; window[c] <= need[c] {
			cnt++
		}
		for cnt == n {
			if r-l+1 < mi {
				mi = r - l + 1
				k = l
			}

			c = s[l]
			if window[c] <= need[c] {
				cnt--
			}
			window[c]--
			l++
		}
	}
	if k < 0 {
		return ""
	}
	return s[k : k+mi]
}

力扣原题 · Doocs 题解来源

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

中等1 种解法

标签：哈希表、字符串、滑动窗口

题目、示例与约束

给你一个字符串 s ，请你找出至多包含 两个不同字符 的最长子串，并返回该子串的长度。

示例 1：

输入：s = "eceba"
输出：3
解释：满足题目要求的子串是 "ece" ，长度为 3 。

示例 2：

输入：s = "ccaabbb"
输出：5
解释：满足题目要求的子串是 "aabbb" ，长度为 5 。

提示：

1 <= s.length <= 10⁵
s 由英文字母组成

方法一：哈希表 + 滑动窗口 · Go 实现

思考

求最多含两种字符的最长子串。 $n \leq 10^{5}$ ，枚举左右端点是 $O (n^{2})$ 。种类数随右端点增加、随左端点减少，具有单调性。右指针纳入字符并计数，种类超过 $2$ 就移动左指针丢掉字符，窗口合法时更新最大长度。

我们维护一个哈希表 cnt 记录当前滑动窗口中各个字符出现的次数，如果哈希表中的键值对个数超过 $2$ ，则说明当前滑动窗口中包含了超过 $2$ 个不同的字符，此时需要移动左指针 j，直到哈希表中的键值对个数不超过 $2$ 为止，然后更新窗口的最大长度。

时间复杂度 $O (n)$ ，空间复杂度 $O (1)$ 。其中 $n$ 为字符串 $s$ 的长度。

func lengthOfLongestSubstringTwoDistinct(s string) (ans int) {
	cnt := map[byte]int{}
	j := 0
	for i := range s {
		cnt[s[i]]++
		for len(cnt) > 2 {
			cnt[s[j]]--
			if cnt[s[j]] == 0 {
				delete(cnt, s[j])
			}
			j++
		}
		ans = max(ans, i-j+1)
	}
	return
}

力扣原题 · Doocs 题解来源

187. 重复的DNA序列

中等2 种解法

标签：位运算、哈希表、字符串、滑动窗口、哈希函数、滚动哈希、Boyer–Moore 算法、扩展 KMP

题目、示例与约束

DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。

例如，"ACGAATTCCG" 是一个 DNA序列 。

在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

示例 1：

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]

示例 2：

输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]

提示：

0 <= s.length <= 10⁵
s[i]=='A'、'C'、'G' or 'T'

方法一：哈希表 · Go 实现

思考

长度为 $10$ 且出现至少两次的子串。 $n \leq 10^{5}$ ，枚举全部子串再两两比较不可行。滑过每个 $s [i . . i + 9]$ ，哈希表计数，第二次出现时写入答案，之后不再重复加入。

我们定义一个哈希表 $c n t$ ，用于存储所有长度为 $10$ 的子字符串出现的次数。

遍历字符串 $s$ 的所有长度为 $10$ 的子字符串，对于当前子字符串 $t$ ，我们更新其在哈希表中对应的计数。如果 $t$ 的计数为 $2$ ，我们就将它加入答案。

遍历结束后，返回答案数组即可。

时间复杂度 $O (n \times 10)$ ，空间复杂度 $O (n \times 10)$ 。其中 $n$ 是字符串 $s$ 的长度。

func findRepeatedDnaSequences(s string) (ans []string) {
	cnt := map[string]int{}
	for i := 0; i < len(s)-10+1; i++ {
		t := s[i : i+10]
		cnt[t]++
		if cnt[t] == 2 {
			ans = append(ans, t)
		}
	}
	return
}

方法二：Rabin-Karp 字符串匹配算法 · Go 实现

思考

方法一每次切片并哈希长度为 $10$ 的串。字母只有四种，可把窗口编成整数，滑窗时加减进出的字符，计数变为 $O (1)$ ，总时间 $O (n)$ 。

本质上是滑动窗口和哈希的结合方法，和 0028.找出字符串中第一个匹配项的下标类似，本题可以借助哈希函数将子序列计数的时间复杂度降低到 $O (1)$ 。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是字符串 $s$ 的长度。

func findRepeatedDnaSequences(s string) []string {
	hashCode := map[byte]int{'A': 0, 'C': 1, 'G': 2, 'T': 3}
	ans, cnt, left, right := []string{}, map[int]int{}, 0, 0

	sha, multi := 0, int(math.Pow(4, 9))
	for ; right < len(s); right++ {
		sha = sha*4 + hashCode[s[right]]
		if right-left+1 < 10 {
			continue
		}
		cnt[sha]++
		if cnt[sha] == 2 {
			ans = append(ans, s[left:right+1])
		}
		sha, left = sha-multi*hashCode[s[left]], left+1
	}
	return ans
}

力扣原题 · Doocs 题解来源

219. 存在重复元素 II

简单1 种解法

标签：数组、哈希表、滑动窗口

题目、示例与约束

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,1], k = 3
输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1
输出：true

示例 3：

输入：nums = [1,2,3,1,2,3], k = 2
输出：false

提示：

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
0 <= k <= 10⁵

方法一：哈希表 · Go 实现

思考

除值相等外，还要求下标差不超过 $k$ 。排序会打乱下标，需额外记录位置。

哈希表保存每个值最近一次出现的下标，扫到相同值时检查间距即可。

我们用一个哈希表 $d$ 存放最近遍历到的数以及对应的下标。

遍历数组 $nums$ ，对于当前遍历到的元素 $nums [i]$ ，如果在哈希表中存在，并且下标与当前元素的下标之差不超过 $k$ ，则返回 $true$ ，否则将当前元素加入哈希表中。

遍历结束后，返回 $false$ 。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为数组 $nums$ 的长度。

func containsNearbyDuplicate(nums []int, k int) bool {
	d := map[int]int{}
	for i, x := range nums {
		if j, ok := d[x]; ok && i-j <= k {
			return true
		}
		d[x] = i
	}
	return false
}

力扣原题 · Doocs 题解来源

220. 存在重复元素 III

困难1 种解法

标签：数组、桶排序、有序集合、排序、滑动窗口

题目、示例与约束

给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。

找出满足下述条件的下标对 (i, j)：

i != j,
abs(i - j) <= indexDiff
abs(nums[i] - nums[j]) <= valueDiff

如果存在，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
输出：true
解释：可以找出 (i, j) = (0, 3) 。
满足下述 3 个条件：
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0

示例 2：

输入：nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
输出：false
解释：尝试所有可能的下标对 (i, j) ，均无法满足这 3 个条件，因此返回 false 。

提示：

2 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
1 <= indexDiff <= nums.length
0 <= valueDiff <= 10⁹

方法一：滑动窗口 + 有序集合 · Go 实现

思考

除下标差不超过 $indexDiff$ 外，还要求值差不超过 $valueDiff$ 。哈希只能判相等，无法在窗口内找“最接近”的数。

维护长度为 $indexDiff$ 的有序集合：对 $v$ 查找不小于 $v - valueDiff$ 的最小元，若它也不超过 $v + valueDiff$ 则成功。随后插入 $v$ ，并删去滑出窗口的元素。

我们维护一个大小为 $k$ 的滑动窗口，窗口中的元素保持有序。

遍历数组 nums，对于每个元素 $n u m s [i]$ ，我们在有序集合中查找第一个大于等于 $n u m s [i] - t$ 的元素，如果元素存在，并且该元素小于等于 $n u m s [i] + t$ ，说明找到了一对符合条件的元素，返回 true。否则，我们将 $n u m s [i]$ 插入到有序集合中，并且如果有序集合的大小超过了 $k$ ，我们需要将最早加入有序集合的元素删除。

时间复杂度 $O (n \times \log k)$ ，其中 $n$ 是数组 nums 的长度。对于每个元素，我们需要 $O (\log k)$ 的时间来查找有序集合中的元素，一共有 $n$ 个元素，因此总时间复杂度是 $O (n \times \log k)$ 。

func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
	n := len(nums)
	left, right := 0, 0
	rbt := redblacktree.NewWithIntComparator()
	for right < n {
		cur := nums[right]
		right++
		if p, ok := rbt.Floor(cur); ok && cur-p.Key.(int) <= t {
			return true
		}
		if p, ok := rbt.Ceiling(cur); ok && p.Key.(int)-cur <= t {
			return true
		}
		rbt.Put(cur, struct{}{})
		if right-left > k {
			rbt.Remove(nums[left])
			left++
		}
	}
	return false
}

力扣原题 · Doocs 题解来源

239. 滑动窗口最大值

困难2 种解法

标签：队列、数组、滑动窗口、单调队列、堆（优先队列）、区间最值查询

题目、示例与约束

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴
1 <= k <= nums.length

方法一：优先队列（大根堆） · Go 实现

思考

每个窗口内再扫一遍求最大，总时间为 $O (n k)$ 。大根堆可在对数时间内给出当前最大，过期下标在堆顶时再弹出。

先放入前 $k - 1$ 个，随后每纳入一个新元素并清理过期堆顶，堆顶即为该窗口最大值。

我们可以使用优先队列（大根堆）来维护滑动窗口中的最大值。

先将前 $k - 1$ 个元素加入优先队列，接下来从第 $k$ 个元素开始，将新元素加入优先队列，同时判断堆顶元素是否滑出窗口，如果滑出窗口则将堆顶元素弹出。然后我们将堆顶元素加入结果数组。

时间复杂度 $O (n \times \log k)$ ，空间复杂度 $O (k)$ 。其中 $n$ 为数组长度。

func maxSlidingWindow(nums []int, k int) (ans []int) {
	q := hp{}
	for i, v := range nums[:k-1] {
		heap.Push(&q, pair{v, i})
	}
	for i := k - 1; i < len(nums); i++ {
		heap.Push(&q, pair{nums[i], i})
		for q[0].i <= i-k {
			heap.Pop(&q)
		}
		ans = append(ans, q[0].v)
	}
	return
}

type pair struct{ v, i int }

type hp []pair

func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool {
	a, b := h[i], h[j]
	return a.v > b.v || (a.v == b.v && i < j)
}
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)   { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any     { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

方法二：单调队列 · Go 实现

思考

堆中会残留过期元素，最坏仍带对数。窗口最大值只关心队头到队尾递减的候选。

单调队列存下标：队头滑出则弹出，队尾不大于当前值则弹出，队头即为窗口最大，线性完成。

求滑动窗口的最大值，一种常见的方法是使用单调队列。

我们可以维护一个从队头到队尾单调递减的队列 $q$ ，队列中存储的是元素的下标。遍历数组 $nums$ ，对于当前元素 $nums [i]$ ，我们首先判断队头元素是否滑出窗口，如果滑出窗口则将队头元素弹出。然后我们将当前元素 $nums [i]$ 从队尾开始依次与队尾元素比较，如果队尾元素小于等于当前元素，则将队尾元素弹出，直到队尾元素大于当前元素或者队列为空。然后将当前元素的下标加入队列。此时队列的队头元素即为当前滑动窗口的最大值，注意，我们将队头元素加入结果数组的时机是当下标 $i$ 大于等于 $k - 1$ 时。

时间复杂度 $O (n)$ ，空间复杂度 $O (k)$ 。其中 $n$ 为数组 $nums$ 的长度。

func maxSlidingWindow(nums []int, k int) (ans []int) {
	q := []int{}
	for i, x := range nums {
		if len(q) > 0 && i-q[0] >= k {
			q = q[1:]
		}
		for len(q) > 0 && nums[q[len(q)-1]] <= x {
			q = q[:len(q)-1]
		}
		q = append(q, i)
		if i >= k-1 {
			ans = append(ans, nums[q[0]])
		}
	}
	return
}

力扣原题 · Doocs 题解来源

340. 至多包含 K 个不同字符的最长子串 🔒

中等1 种解法

标签：哈希表、字符串、滑动窗口

题目、示例与约束

给你一个字符串 s 和一个整数 k ，请你找出至多包含 k 个不同字符的最长子串，并返回该子串的长度。

示例 1：

输入：s = "eceba", k = 2
输出：3
解释：满足题目要求的子串是 "ece" ，长度为 3 。

示例 2：

输入：s = "aa", k = 1
输出：2
解释：满足题目要求的子串是 "aa" ，长度为 2 。

提示：

1 <= s.length <= 5 * 10⁴
0 <= k <= 50

方法一：滑动窗口 + 哈希表 · Go 实现

思考

至多 $k$ 种不同字符的最长子串。枚举左右端点再数种类为 $O (n^{2})$ 。种类数随右端点增加、随左端点右移减少，可用滑动窗口。

右指针纳入字符；种类超过 $k$ 时左端删减直至合法。窗口始终是「以当前右端为尾的最长合法段」，最终长度即 $n - l$ 。

我们可以使用滑动窗口的思想，用一个哈希表 $cnt$ 记录窗口中每个字符的出现次数，用 $l$ 记录窗口的左边界。

遍历字符串，每次将右边界的字符加入哈希表，如果哈希表中不同字符的个数超过了 $k$ ，则将左边界的字符从哈希表中删除，然后更新左边界 $l$ 。

最后返回字符串的长度减去左边界的长度即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (k)$ 。其中 $n$ 为字符串的长度。

func lengthOfLongestSubstringKDistinct(s string, k int) int {
	cnt := map[byte]int{}
	l := 0
	for _, c := range s {
		cnt[byte(c)]++
		if len(cnt) > k {
			cnt[s[l]]--
			if cnt[s[l]] == 0 {
				delete(cnt, s[l])
			}
			l++
		}
	}
	return len(s) - l
}

力扣原题 · Doocs 题解来源

395. 至少有 K 个重复字符的最长子串

中等1 种解法

标签：哈希表、字符串、分治、滑动窗口

题目、示例与约束

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串，要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

如果不存在这样的子字符串，则返回 0。

示例 1：

输入：s = "aaabb", k = 3
输出：3
解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。

示例 2：

输入：s = "ababbc", k = 2
输出：5
解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。

提示：

1 <= s.length <= 10⁴
s 仅由小写英文字母组成
1 <= k <= 10⁵

方法一：分治 · Go 实现

思考

最长子串使得其中每个出现过的字符次数都 $\geq k$ 。滑动窗口的种类约束不直接对应「每个都够 $k$ 次」。若某字符全局不足 $k$ ，则含它的串一律非法，可作分割点。

统计区间内频次，找出一个不足 $k$ 的字符，按它切开递归；若没有这样的字符则整段合法。最深 $26$ 层。

对于字符串 $s$ ，如果存在某个字符 $c$ ，其出现次数小于 $k$ ，则任何包含 $c$ 的子串都不可能满足题目要求。因此我们可以将 $s$ 按照每个不满足条件的字符 $c$ 进行分割，分割得到的每个子串都是原字符串的一个「子问题」，我们可以递归地求解每个子问题，最终的答案即为所有子问题的最大值。

时间复杂度 $O (n \times C)$ ，空间复杂度 $O (C^{2})$ 。其中 $n$ 为字符串 $s$ 的长度，而 $C$ 为字符集的大小。本题中 $C \leq 26$ 。

func longestSubstring(s string, k int) int {
	var dfs func(l, r int) int
	dfs = func(l, r int) int {
		cnt := [26]int{}
		for i := l; i <= r; i++ {
			cnt[s[i]-'a']++
		}
		var split byte
		for i, v := range cnt {
			if v > 0 && v < k {
				split = byte(i + 'a')
				break
			}
		}
		if split == 0 {
			return r - l + 1
		}
		i := l
		ans := 0
		for i <= r {
			for i <= r && s[i] == split {
				i++
			}
			if i > r {
				break
			}
			j := i
			for j <= r && s[j] != split {
				j++
			}
			t := dfs(i, j-1)
			ans = max(ans, t)
			i = j
		}
		return ans
	}
	return dfs(0, len(s)-1)
}

力扣原题 · Doocs 题解来源

424. 替换后的最长重复字符

中等1 种解法

标签：哈希表、字符串、滑动窗口

题目、示例与约束

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。

在执行上述操作后，返回 包含相同字母的最长子字符串的长度。

示例 1：

输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。

示例 2：

输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
可能存在其他的方法来得到同样的结果。

提示：

1 <= s.length <= 10⁵
s 仅由大写英文字母组成
0 <= k <= s.length

方法一：双指针 · Go 实现

思考

窗口内最多修改 $k$ 个字符使之全相同，即「窗口长度减去众数次数 $\leq k$ 」。枚举左右端点是 $O (n^{2})$ ， $n \leq 10^{4}$ 偏紧。

右指针扩张并维护窗口内最大频次 $mx$ ；当 $r - l + 1 - mx > k$ 时左端右移一格。只需最大合法窗口，答案为 $n - l$ 。

左移时不必减小 $mx$ ：窗口只关心最大长度，偏大的 $mx$ 只会使判定更严，不会漏掉更长的合法段。

我们使用一个哈希表 cnt 统计字符串中每个字符出现的次数，使用双指针 l 和 r 维护一个滑动窗口，使得窗口的大小减去出现次数最多的字符的次数，结果不超过 $k$ 。

我们遍历字符串，每次更新窗口的右边界 r，并更新窗口内的字符出现次数，同时更新出现过的字符的最大出现次数 mx。当窗口的大小减去 mx 大于 $k$ 时，我们需要缩小窗口的左边界 l，同时更新窗口内的字符出现次数，直到窗口的大小减去 mx 不大于 $k$ 。

最后，答案为 $n - l$ ，其中 $n$ 为字符串的长度。

时间复杂度 $O (n)$ ，空间复杂度 $O (| Σ |)$ 。其中 $n$ 为字符串的长度，而 $| Σ |$ 为字符集的大小，本题中字符集为大写英文字母，所以 $| Σ | = 26$ 。

func characterReplacement(s string, k int) int {
	cnt := [26]int{}
	l, mx := 0, 0
	for r, c := range s {
		cnt[c-'A']++
		mx = max(mx, cnt[c-'A'])
		if r-l+1-mx > k {
			cnt[s[l]-'A']--
			l++
		}
	}
	return len(s) - l
}

力扣原题 · Doocs 题解来源

438. 找到字符串中所有字母异位词

中等2 种解法

标签：哈希表、字符串、滑动窗口

题目、示例与约束

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

1 <= s.length, p.length <= 3 * 10⁴
s 和 p 仅包含小写字母

方法一：滑动窗口 · Go 实现

思考

异位词是字母计数相同的等长子串。枚举每个起点再排序比较过慢。

固定长度 $n = | p |$ 的窗口，维护窗口计数与 $p$ 的计数，相等则记录左端。先放入前 $n - 1$ 个字符，右端每进一步比较并弹出左端。

窗口长度始终为 $n$ ，只需比较两个长度为 $26$ 的计数。

我们不妨设字符串 $s$ 的长度为 $m$ ，字符串 $p$ 的长度为 $n$ 。

如果 $m < n$ ，那么 $s$ 中不可能存在任何一个子串同 $p$ 为异位词，返回空列表即可。

当 $m \geq n$ 时，我们可以使用一个固定长度为 $n$ 的滑动窗口来维护 $s$ 的子串。为了判断子串是否为 $p$ 的异位词，我们可以用一个固定长度为 $26$ 的数组 $c n t 1$ 记录 $p$ 中每个字母的出现次数，再用另一个数组 $c n t 2$ 记录当前滑动窗口中每个字母的出现次数，如果这两个数组相同，那么当前滑动窗口的子串就是 $p$ 的异位词，我们记录下起始位置。

时间复杂度 $O (m \times C)$ ，空间复杂度 $O (C)$ 。其中 $m$ 是字符串 $s$ 的长度；而 $C$ 是字符集大小，在本题中字符集为所有小写字母，所以 $C = 26$ 。

func findAnagrams(s string, p string) (ans []int) {
	m, n := len(s), len(p)
	if m < n {
		return
	}
	cnt1 := [26]int{}
	cnt2 := [26]int{}
	for _, c := range p {
		cnt1[c-'a']++
	}
	for _, c := range s[:n-1] {
		cnt2[c-'a']++
	}
	for i := n - 1; i < m; i++ {
		cnt2[s[i]-'a']++
		if cnt1 == cnt2 {
			ans = append(ans, i-n+1)
		}
		cnt2[s[i-n+1]-'a']--
	}
	return
}

方法二：双指针（滑动窗口优化） · Go 实现

思考

方法一每次比较整个计数数组。改为右端加入后，若某字母超出 $p$ 的配额则左端收缩，窗口内每字母都不超额。此时长度恰为 $n$ 即异位词。

比较从 $O (| Σ |)$ 变成检查长度，滑动过程仍是线性。

我们可以对方法一进行优化，与方法一类似，我们用一个固定长度为 $26$ 的数组 $c n t 1$ 记录 $p$ 中每个字母的出现次数，用另一个数组 $c n t 2$ 记录当前滑动窗口中每个字母的出现次数，用指针 $i$ 和 $j$ 分别指向滑动窗口的左右边界。每一次移动指针 $j$ ，将 $c n t 2 [s [j]]$ 的值加 $1$ ，如果当前 $c n t 2 [s [j]]$ 的值大于 $c n t 1 [s [j]]$ ，则将指针 $i$ 不断右移，直到 $c n t 2 [s [j]]$ 的值不大于 $c n t 1 [s [j]]$ 。此时，如果滑动窗口的长度等于 $p$ 的长度，我们就找到了一个异位词，将起始位置加入答案。继续移动指针 $j$ ，重复上述操作，直到指针 $j$ 移动到 $s$ 的末尾。

时间复杂度 $O (m + n)$ ，空间复杂度 $O (C)$ 。其中 $m$ 和 $n$ 分别是字符串 $s$ 和 $p$ 的长度；而 $C$ 是字符集大小，在本题中字符集为所有小写字母，所以 $C = 26$ 。

func findAnagrams(s string, p string) (ans []int) {
	m, n := len(s), len(p)
	if m < n {
		return
	}
	cnt1 := [26]int{}
	cnt2 := [26]int{}
	for _, c := range p {
		cnt1[c-'a']++
	}
	j := 0
	for i, c := range s {
		cnt2[c-'a']++
		for cnt2[c-'a'] > cnt1[c-'a'] {
			cnt2[s[j]-'a']--
			j++
		}
		if i-j+1 == n {
			ans = append(ans, j)
		}
	}
	return
}

力扣原题 · Doocs 题解来源

480. 滑动窗口中位数

困难2 种解法

标签：数组、哈希表、树堆、滑动窗口、堆（优先队列）

题目、示例与约束

中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。

例如：

[2,3,4]，中位数是 3
[2,3]，中位数是 (2 + 3) / 2 = 2.5

给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

示例：

给出 nums = [1,3,-1,-3,5,3,6,7]，以及 k = 3。

窗口位置                      中位数
---------------               -----
[1  3  -1] -3  5  3  6  7       1
 1 [3  -1  -3] 5  3  6  7      -1
 1  3 [-1  -3  5] 3  6  7      -1
 1  3  -1 [-3  5  3] 6  7       3
 1  3  -1  -3 [5  3  6] 7       5
 1  3  -1  -3  5 [3  6  7]      6

因此，返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]。

提示：

你可以假设 k 始终有效，即：k 始终小于等于输入的非空数组的元素个数。
与真实值误差在 10 ^ -5 以内的答案将被视作正确答案。

方法一：双优先队列（大小根堆） + 延迟删除 · Go 实现

思考

滑动窗口中位数。每次排序窗口是 $O (n k \log k)$ 。堆可以维护中位数，但堆不能任意删除离开窗口的元素。

对顶堆：大根堆存较小一半，小根堆存较大一半，另用哈希表延迟删除。加入、弹出后只在堆顶清理过期值，再平衡两边的有效大小。

延迟删除把「任意删」变成堆顶弹出；有效大小用计数维护，堆顶始终是当前中位数的候选。

我们可以使用两个优先队列（大小根堆）维护当前窗口中的元素，其中一个优先队列存储当前窗口中较小的一半元素，另一个优先队列存储当前窗口中较大的一半元素。这样，当前窗口的中位数就是两个优先队列的堆顶元素的平均值或其中的一个。

我们设计一个类 $MedianFinder$ ，用于维护当前窗口中的元素。该类包含以下方法：

add_num(num)：将 $num$ 加入当前窗口中。
find_median()：返回当前窗口中元素的中位数。
remove_num(num)：将 $num$ 从当前窗口中移除。
prune(pq)：如果堆顶元素在延迟删除字典 $delayed$ 中，则将其从堆顶弹出，并从该元素的延迟删除次数中减一。如果该元素的延迟删除次数为零，则将其从延迟删除字典中删除。
rebalance()：如果较小的一半元素的数量比较大的一半元素的数量多 $2$ 个，则将较大的一半元素的堆顶元素加入较小的一半元素中；如果较小的一半元素的数量比较大的一半元素的数量少，则将较大的一半元素的堆顶元素加入较小的一半元素中。

在 add_num(num) 方法中，我们先考虑将 $num$ 加入较小的一半元素中，如果 $num$ 大于较大的一半元素的堆顶元素，则将 $num$ 加入较大的一半元素中。然后我们调用 rebalance() 方法，使得两个优先队列的大小之差不超过 $1$ 。

在 remove_num(num) 方法中，我们将 $num$ 的延迟删除次数加一。然后我们将 $num$ 与较小的一半元素的堆顶元素进行比较，如果 $num$ 小于等于较小的一半元素的堆顶元素，则更新较小的一半元素的大小，并且调用 prune() 方法，使得较小的一半元素的堆顶元素不在延迟删除字典中。否则，我们更新较大的一半元素的大小，并且调用 prune() 方法，使得较大的一半元素的堆顶元素不在延迟删除字典中。

在 find_median() 方法中，如果当前窗口的大小为奇数，则返回较小的一半元素的堆顶元素；否则，返回较小的一半元素的堆顶元素与较大的一半元素的堆顶元素的平均值。

在 prune(pq) 方法中，如果堆顶元素在延迟删除字典中，则将其从堆顶弹出，并从该元素的延迟删除次数中减一。如果该元素的延迟删除次数为零，则将其从延迟删除字典中删除。

在 rebalance() 方法中，如果较小的一半元素的数量比较大的一半元素的数量多 $2$ 个，则将较大的一半元素的堆顶元素加入较小的一半元素中；如果较小的一半元素的数量比较大的一半元素的数量少，则将较大的一半元素的堆顶元素加入较小的一半元素中。

时间复杂度 $O (n \times \log n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为数组 $nums$ 的长度。

type MedianFinder struct {
	small                hp
	large                hp
	delayed              map[int]int
	smallSize, largeSize int
	k                    int
}

func Constructor(k int) MedianFinder {
	return MedianFinder{hp{}, hp{}, map[int]int{}, 0, 0, k}
}

func (this *MedianFinder) AddNum(num int) {
	if this.small.Len() == 0 || num <= -this.small.IntSlice[0] {
		heap.Push(&this.small, -num)
		this.smallSize++
	} else {
		heap.Push(&this.large, num)
		this.largeSize++
	}
	this.rebalance()
}

func (this *MedianFinder) FindMedian() float64 {
	if this.k&1 == 1 {
		return float64(-this.small.IntSlice[0])
	}
	return float64(-this.small.IntSlice[0]+this.large.IntSlice[0]) / 2
}

func (this *MedianFinder) removeNum(num int) {
	this.delayed[num]++
	if num <= -this.small.IntSlice[0] {
		this.smallSize--
		if num == -this.small.IntSlice[0] {
			this.prune(&this.small)
		}
	} else {
		this.largeSize--
		if num == this.large.IntSlice[0] {
			this.prune(&this.large)
		}
	}
	this.rebalance()
}

func (this *MedianFinder) prune(pq *hp) {
	sign := 1
	if pq == &this.small {
		sign = -1
	}
	for pq.Len() > 0 && this.delayed[sign*pq.IntSlice[0]] > 0 {
		this.delayed[sign*pq.IntSlice[0]]--
		if this.delayed[sign*pq.IntSlice[0]] == 0 {
			delete(this.delayed, sign*pq.IntSlice[0])
		}
		heap.Pop(pq)
	}
}

func (this *MedianFinder) rebalance() {
	if this.smallSize > this.largeSize+1 {
		heap.Push(&this.large, -heap.Pop(&this.small).(int))
		this.smallSize--
		this.largeSize++
		this.prune(&this.small)
	} else if this.smallSize < this.largeSize {
		heap.Push(&this.small, -heap.Pop(&this.large).(int))
		this.smallSize++
		this.largeSize--
		this.prune(&this.large)
	}
}

func medianSlidingWindow(nums []int, k int) []float64 {
	finder := Constructor(k)
	for _, num := range nums[:k] {
		finder.AddNum(num)
	}
	ans := []float64{finder.FindMedian()}
	for i := k; i < len(nums); i++ {
		finder.AddNum(nums[i])
		finder.removeNum(nums[i-k])
		ans = append(ans, finder.FindMedian())
	}
	return ans
}

type hp struct{ sort.IntSlice }

func (h hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] }
func (h *hp) Push(v any)        { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
	a := h.IntSlice
	v := a[len(a)-1]
	h.IntSlice = a[:len(a)-1]
	return v
}

方法二：有序集合 · Go 实现

思考

方法一的延迟删除实现较长。有序集合支持 $O (\log k)$ 插入删除。左边集合存较小一半，右边存较大一半，每次先入右再把最小移到左并平衡。窗口满后读两端，再删滑出的值。

代码更短，代价是需要有序表结构。

我们可以用两个有序集合来维护当前窗口中的元素，其中有序集合 $l$ 存储当前窗口中较小的一半元素，有序集合 $r$ 存储当前窗口中较大的一半元素。

遍历数组 $nums$ ，对于每个元素 $x$ ，我们将其加入有序集合 $r$ ，然后将有序集合 $r$ 的最小值加入有序集合 $l$ 。如果有序集合 $l$ 的大小比有序集合 $r$ 的大小大于 $1$ ，我们将有序集合 $l$ 的最大值加入有序集合 $r$ 。

如果当前窗口元素总数为 $k$ ，大小为奇数，则有序集合 $l$ 的最大值就是中位数；如果当前窗口的大小为偶数，则有序集合 $l$ 的最大值和有序集合 $r$ 的最小值的平均值就是中位数。然后，我们将窗口的最左边元素移除，继续遍历数组。

时间复杂度 $O (n \log k)$ ，空间复杂度 $O (k)$ 。其中 $n$ 为数组 $nums$ 的长度。

func medianSlidingWindow(nums []int, k int) (ans []float64) {
	l := redblacktree.New[int, int]()
	r := redblacktree.New[int, int]()
	merge := func(st *redblacktree.Tree[int, int], x, v int) {
		c, _ := st.Get(x)
		if c+v == 0 {
			st.Remove(x)
		} else {
			st.Put(x, c+v)
		}
	}
	lSize, rSize := 0, 0
	for i, x := range nums {
		merge(r, x, 1)
		x = r.Left().Key
		merge(r, x, -1)
		merge(l, x, 1)
		lSize++
		for lSize-rSize > 1 {
			x = l.Right().Key
			merge(l, x, -1)
			merge(r, x, 1)
			lSize--
			rSize++
		}
		if j := i - k + 1; j >= 0 {
			if k%2 == 1 {
				ans = append(ans, float64(l.Right().Key))
			} else {
				ans = append(ans, float64(l.Right().Key+r.Left().Key)/2)
			}
			if x = nums[j]; x <= l.Right().Key {
				merge(l, x, -1)
				lSize--
			} else {
				merge(r, x, -1)
				rSize--
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

567. 字符串的排列

中等1 种解法

标签：哈希表、双指针、字符串、滑动窗口

题目、示例与约束

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的子串。

示例 1：

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

示例 2：

输入：s1= "ab" s2 = "eidboaoo"
输出：false

提示：

1 <= s1.length, s2.length <= 10⁴
s1 和 s2 仅包含小写字母

方法一：滑动窗口 · Go 实现

思考

判断 $s 2$ 是否包含 $s 1$ 的某个排列，即是否存在长度 $| s 1 |$ 的窗口与 $s 1$ 字母计数相同。枚举窗口再排序比较偏慢。

滑动窗口维护与 $s 1$ 的差额计数，并用 $need$ 记录尚有多少字符未对齐。右端纳入、左端滑出，当 $need = 0$ 即找到排列。窗口长度固定，一次扫描完成。

我们用一个数组 $cnt$ 记录当前需要匹配的字符及其个数，用一个变量 $need$ 记录当前还需要匹配的字符种类数，初始时 $cnt$ 为字符串 $s1$ 中各字符出现次数，而 $need$ 为 $s1$ 中不同字符的个数。

然后我们遍历字符串 $s2$ ，对于每个字符，我们将其在 $cnt$ 中的对应值减一，如果减一后的值等于 $0$ ，说明当前字符在 $s1$ 中出现次数已经满足要求，我们将 $need$ 减一。如果当前下标 $i$ 大于等于 $s1$ 的长度，我们需要将 $s2 [i - s1] cnt$ 中对应值加一，如果加一后的值等于 $1$ ，说明当前字符在 $s1$ 中出现次数不再满足要求，我们将 $need$ 加一。在遍历过程中，如果 $need$ 的值等于 $0$ ，说明所有字符的出现次数都满足要求，我们就找到了一个满足要求的子串，返回 $true$ 。

否则，如果遍历结束后没有找到满足要求的子串，我们返回 $false$ 。

时间复杂度 $O (m + n)$ ，其中 $m$ 和 $n$ 分别是字符串 $s1$ 和 $s2$ 的长度。空间复杂度 $O (| Σ |)$ ，其中 $Σ$ 是字符集，这道题中字符集为小写字母，所以空间复杂度是常数级别的。

func checkInclusion(s1 string, s2 string) bool {
	need := 0
	cnt := [26]int{}

	for _, c := range s1 {
		if cnt[c-'a']++; cnt[c-'a'] == 1 {
			need++
		}
	}

	m, n := len(s1), len(s2)
	for i := 0; i < n; i++ {
		c := s2[i] - 'a'
		if cnt[c]--; cnt[c] == 0 {
			need--
		}
		if i >= m {
			c = s2[i-m] - 'a'
			if cnt[c]++; cnt[c] == 1 {
				need++
			}
		}
		if need == 0 {
			return true
		}
	}
	return false
}

力扣原题 · Doocs 题解来源

594. 最长和谐子序列

简单1 种解法

标签：数组、哈希表、计数、排序、滑动窗口

题目、示例与约束

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。

给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。

数组的 子序列 是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

示例 1：

输入：nums = [1,3,2,2,5,2,3,7]

输出：5

解释：

最长和谐子序列是 [3,2,2,2,3]。

示例 2：

输入：nums = [1,2,3,4]

输出：2

解释：

最长和谐子序列是 [1,2]，[2,3] 和 [3,4]，长度都为 2。

示例 3：

输入：nums = [1,1,1,1]

输出：0

解释：

不存在和谐子序列。

提示：

1 <= nums.length <= 2 * 10⁴
-10⁹ <= nums[i] <= 10⁹

方法一：哈希表 · Go 实现

思考

和谐子序列的最大值与最小值之差恰为 $1$ 。子序列可打乱顺序，因此只关心取值。枚举所有子序列不现实。

计数每个值的出现次数。对每个 $x$ ，若 $x + 1$ 也出现，则 $c n t [x] + c n t [x + 1]$ 就是以这两值为元素的最长和谐子序列。取这些长度的最大。

我们可以用一个哈希表 $cnt$ 记录数组 $nums$ 中每个元素出现的次数，然后遍历哈希表中的每个键值对 $(x, c)$ ，如果哈希表中存在键 $x + 1$ ，那么 $nums$ 中元素 $x$ 和 $x + 1$ 出现的次数之和 $c + cnt [x + 1]$ 就是一个和谐子序列，我们只需要在所有和谐子序列中找到最大的长度即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为数组 $nums$ 的长度。

func findLHS(nums []int) (ans int) {
	cnt := map[int]int{}
	for _, x := range nums {
		cnt[x]++
	}
	for x, c := range cnt {
		if c1, ok := cnt[x+1]; ok {
			ans = max(ans, c+c1)
		}
	}
	return
}

力扣原题 · Doocs 题解来源

643. 子数组最大平均数 I

简单1 种解法

标签：数组、滑动窗口

题目、示例与约束

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

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

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

示例 1：

输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

示例 2：

输入：nums = [5], k = 1
输出：5.00000

提示：

n == nums.length
1 <= k <= n <= 10⁵
-10⁴ <= nums[i] <= 10⁴

方法一：滑动窗口 · Go 实现

思考

定长 $k$ 子数组的最大平均值等价于最大和。每次重算窗口是 $O (n k)$ ， $n$ 可达 $10^{5}$ 。

维护长度为 $k$ 的滑动和，右端加入、左端减去，记录最大和再除以 $k$ 。

我们维护一个长度为 $k$ 的滑动窗口，每次计算窗口内的和 $s$ ，取最大的和 $s$ 作为答案。

时间复杂度 $O (n)$ ，其中 $n$ 是数组 $n u m s$ 的长度。空间复杂度 $O (1)$ 。

func findMaxAverage(nums []int, k int) float64 {
	s := 0
	for _, x := range nums[:k] {
		s += x
	}
	ans := s
	for i := k; i < len(nums); i++ {
		s += nums[i] - nums[i-k]
		ans = max(ans, s)
	}
	return float64(ans) / float64(k)
}

力扣原题 · Doocs 题解来源

904. 水果成篮

中等2 种解法

标签：数组、哈希表、滑动窗口

题目、示例与约束

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

你只有两个篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从每棵树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的最大数目。

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

提示：

1 <= fruits.length <= 10⁵
0 <= fruits[i] < fruits.length

方法一：哈希表 + 滑动窗口 · Go 实现

思考

所求为至多含两种水果的最长子数组。 $n \leq 10^{5}$ ，枚举左右端点再统计种类不可行。右端每纳入一种水果，种类超过 $2$ 时必须右移左端。

用计数表维护窗口内各水果个数，种类由哈希表大小给出；每当种类大于 $2$ 就弹出左端，并记录窗口长度的最大值。

我们用哈希表 $cnt$ 维护当前窗口内的水果种类以及对应的数量，用双指针 $j$ 和 $i$ 维护窗口的左右边界。

遍历数组 $fruits$ ，将当前水果 $x$ 加入窗口，即 $cnt [x] + +$ ，然后判断当前窗口内的水果种类是否超过了 $2$ 种，如果超过了 $2$ 种，就需要将窗口的左边界 $j$ 右移，直到窗口内的水果种类不超过 $2$ 种为止。然后更新答案，即 $ans = max (ans, i - j + 1)$ 。

遍历结束后，即可得到最终的答案。

1 2 3 2 2 1 4
^   ^
j   i


1 2 3 2 2 1 4
  ^ ^
  j i


1 2 3 2 2 1 4
  ^     ^
  j     i

时间复杂度 $O (n)$ ，其中 $n$ 为数组 $fruits$ 的长度。空间复杂度 $O (1)$ ，因为哈希表 $cnt$ 中的键值对数量最多为 $2$ 。

func totalFruit(fruits []int) int {
	cnt := map[int]int{}
	ans, j := 0, 0
	for i, x := range fruits {
		cnt[x]++
		for ; len(cnt) > 2; j++ {
			y := fruits[j]
			cnt[y]--
			if cnt[y] == 0 {
				delete(cnt, y)
			}
		}
		ans = max(ans, i-j+1)
	}
	return ans
}

方法二：单调变长滑动窗口 · Go 实现

思考

方法一在种类超限时缩小窗口并反复更新答案，但题目只要最大长度，历史更短的窗口不必保留。窗口只增不减：种类超过 $2$ 时左端同步前进一步，遍历结束时 $n - j$ 即为最大可行窗口。

在方法一中，我们发现，窗口大小会时而变大，时而变小，这就需要我们每一次更新答案。

但本题实际上求的是水果的最大数目，也就是“最大”的窗口，我们没有必要缩小窗口，只需要让窗口单调增大。于是代码就少了每次更新答案的操作，只需要在遍历结束后将此时的窗口大小作为答案返回即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为数组 $fruits$ 的长度。

func totalFruit(fruits []int) int {
	cnt := map[int]int{}
	j := 0
	for _, x := range fruits {
		cnt[x]++
		if len(cnt) > 2 {
			y := fruits[j]
			cnt[y]--
			if cnt[y] == 0 {
				delete(cnt, y)
			}
			j++
		}
	}
	return len(fruits) - j
}

力扣原题 · Doocs 题解来源

930. 和相同的二元子数组

中等2 种解法

标签：数组、哈希表、前缀和、滑动窗口

题目、示例与约束

给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的非空子数组。

子数组 是数组的一段连续部分。

示例 1：

输入：nums = [1,0,1,0,1], goal = 2
输出：4
解释：
有 4 个满足题目要求的子数组：[1,0,1]、[1,0,1,0]、[0,1,0,1]、[1,0,1]

示例 2：

输入：nums = [0,0,0,0,0], goal = 0
输出：15

提示：

1 <= nums.length <= 3 * 10⁴
nums[i] 不是 0 就是 1
0 <= goal <= nums.length

方法一：数组或哈希表 + 前缀和 · Go 实现

思考

求元素为 $0 / 1$ 的数组中和为 $goal$ 的子数组个数。 $n$ 较大，不能枚举区间。前缀和 $s$ 出现时，左端满足 $s - goal$ 的前缀个数即为以当前为右端的答案。用计数表维护前缀出现次数，初始 $c n t [0] = 1$ 。

我们可以用数组或哈希表 $c n t$ 记录每个前缀和出现的次数，其中 $c n t [i]$ 表示前缀和为 $i$ 的子数组个数。初始时 $c n t [0] = 1$ 。

接下来我们遍历数组 nums，用变量 $s$ 维护当前的前缀和，对于每个 $s$ ，我们可以计算出 $s - g o a l$ 出现的次数，即为以当前位置结尾的满足条件的子数组个数，累加到答案中。然后我们将 $s$ 的计数值加 $1$ 。

最终的答案即为满足条件的子数组个数。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为数组 nums 的长度。

func numSubarraysWithSum(nums []int, goal int) (ans int) {
	cnt := map[int]int{0: 1}
	s := 0
	for _, v := range nums {
		s += v
		ans += cnt[s-goal]
		cnt[s]++
	}
	return
}

方法二：双指针 · Go 实现

思考

方法一需要线性额外空间。数组非负，窗口和随右端单调，可用两条左指针分别维护和大于 $goal$ 与和至少为 $goal$ 的边界，两者之差即和恰为 $goal$ 的子数组个数，额外空间为常数。

func numSubarraysWithSum(nums []int, goal int) int {
	i1, i2, s1, s2, j, ans, n := 0, 0, 0, 0, 0, 0, len(nums)
	for j < n {
		s1 += nums[j]
		s2 += nums[j]
		for i1 <= j && s1 > goal {
			s1 -= nums[i1]
			i1++
		}
		for i2 <= j && s2 >= goal {
			s2 -= nums[i2]
			i2++
		}
		ans += i2 - i1
		j++
	}
	return ans
}

力扣原题 · Doocs 题解来源

992. K 个不同整数的子数组

困难1 种解法

标签：数组、哈希表、计数、滑动窗口

题目、示例与约束

给定一个正整数数组 nums和一个整数 k，返回 nums 中「好子数组」 的数目。

如果 nums 的某个子数组中不同整数的个数恰好为 k，则称 nums 的这个连续、不一定不同的子数组为「好子数组」。

例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。

子数组 是数组的连续部分。

示例 1：

输入：nums = [1,2,1,2,3], k = 2
输出：7
解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

示例 2：

输入：nums = [1,2,1,3,4], k = 3
输出：3
解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].

提示：

1 <= nums.length <= 2 * 10⁴
1 <= nums[i], k <= nums.length

方法一：双指针 · Go 实现

思考

恰含 $k$ 种整数的子数组个数。 $n \leq 2 \times 10^{4}$ ，不能枚举。种类数随窗口单调，于是“至多 $k$ 种”可用滑动窗口。恰为 $k$ 种等于“至多 $k$ 种的最左端”减去“至多 $k - 1$ 种的最左端”，对每个右端点求和。

我们遍历数组 $n u m s$ ，对于每个 $i$ ，我们需要找到最小的 $j_{1}$ ，使得 $n u m s [j_{1}], n u m s [j_{1} + 1], \dots, n u m s [i]$ 中不同的整数个数小于等于 $k$ ，以及最小的 $j_{2}$ ，使得 $n u m s [j_{2}], n u m s [j_{2} + 1], \dots, n u m s [i]$ 中不同的整数个数小于等于 $k - 1$ 。那么 $j_{2} - j_{1}$ 就是以 $i$ 结尾的满足条件的子数组的个数。

在实现上，我们定义一个函数 $f (k)$ ，表示 $n u m s$ 中每个位置 $i$ 对应的最小的 $j$ ，使得 $n u m s [j], n u m s [j + 1], \dots, n u m s [i]$ 中不同的整数个数小于等于 $k$ 。该函数可以通过双指针实现，具体实现见代码。

然后我们调用 $f (k)$ 和 $f (k - 1)$ ，计算出每个位置对应的 $j_{1}$ 和 $j_{2}$ ，然后计算出以每个位置 $i$ 结尾的满足条件的子数组的个数，最后求和即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为数组 $n u m s$ 的长度。

func subarraysWithKDistinct(nums []int, k int) (ans int) {
	f := func(k int) []int {
		n := len(nums)
		pos := make([]int, n)
		cnt := make([]int, n+1)
		s, j := 0, 0
		for i, x := range nums {
			cnt[x]++
			if cnt[x] == 1 {
				s++
			}
			for ; s > k; j++ {
				cnt[nums[j]]--
				if cnt[nums[j]] == 0 {
					s--
				}
			}
			pos[i] = j
		}
		return pos
	}
	left, right := f(k), f(k-1)
	for i := range left {
		ans += right[i] - left[i]
	}
	return
}

力扣原题 · Doocs 题解来源

995. K 连续位的最小翻转次数

困难2 种解法

标签：位运算、队列、数组、前缀和、滑动窗口

题目、示例与约束

给定一个二进制数组 nums 和一个整数 k 。

k位翻转 就是从 nums 中选择一个长度为 k 的 子数组 ，同时把子数组中的每一个 0 都改成 1 ，把子数组中的每一个 1 都改成 0 。

返回数组中不存在 0 所需的最小 k位翻转 次数。如果不可能，则返回 -1 。

子数组 是数组的连续部分。

示例 1：

输入：nums = [0,1,0], K = 1
输出：2
解释：先翻转 A[0]，然后翻转 A[2]。

示例 2：

输入：nums = [1,1,0], K = 2
输出：-1
解释：无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。

示例 3：

输入：nums = [0,0,0,1,0,1,1,0], K = 3
输出：3
解释：
翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0]
翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0]
翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1]

提示：

1 <= nums.length <= 10⁵
1 <= k <= nums.length

方法一：差分数组 · Go 实现

思考

每次翻转长度为 $k$ 的连续段，使全数组变为 $1$ ，次数最少。 $n \leq 10^{5}$ ，不能模拟每次翻转。从左到右贪心：当前位在此前翻转次数后仍为 $0$ ，则必须在此开一段。差分数组 $O (1)$ 标记 $[i, i + k)$ 的翻转。

我们注意到，对于若干个连续的元素进行反转，其结果与对这些元素进行反转的次序无关。因此我们可以贪心地考虑每个位置需要进行反转的次数。

我们不妨从左到右处理数组。

假设当前我们需要处理位置 $i$ ，而位置 $i$ 左侧的元素已经被处理完毕，如果 $i$ 位置的元素为 $0$ ，那么我们必须进行反转操作，我们需要将 $[i, . . i + k - 1]$ 区间内的元素进行反转。这里我们用一个差分数组 $d$ 来维护每个位置的反转次数，那么判断当前位置 $i$ 是否需要反转，只需要看 $s = \sum_{j = 0}^{i} d [j]$ 以及 $n u m s [i]$ 的奇偶性，如果 $s$ 与 $n u m s [i]$ 奇偶性相同，那么位置 $i$ 的元素仍然为 $0$ ，需要进行反转。此时我们判断一下 $i + k$ 是否超出了数组的长度，如果超出了数组的长度，那么就无法完成目标，返回 $- 1$ 。否则我们令 $d [i]$ 增加 $1$ ，同时令 $d [i + k]$ 减少 $1$ ，然后将答案增加 $1$ ，并且 $s$ 增加 $1$ 。

这样当我们处理完数组中的所有元素时，返回答案即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。这里 $n$ 是数组 $n u m s$ 的长度。

func minKBitFlips(nums []int, k int) (ans int) {
	n := len(nums)
	d := make([]int, n+1)
	s := 0
	for i, x := range nums {
		s += d[i]
		if s%2 == x {
			if i+k > n {
				return -1
			}
			d[i]++
			d[i+k]--
			s++
			ans++
		}
	}
	return
}

方法二：滑动窗口 · Go 实现

思考

差分数组需要线性额外空间。用变量记录当前奇偶，并把翻转起点标成 $- 1$ ，窗口滑出时异或回去，即可在原数组上 $O (1)$ 空间完成同样贪心。

我们可以用一个变量 $flipped$ 来表示当前位置是否翻转，如果 $flipped$ 为 $1$ ，表示当前位置已经翻转，否则表示当前位置未翻转。对于翻转过的位置，我们可以将其值设置为 $- 1$ ，这样我们就可以区分出哪些位置已经翻转过了。

接下来我们从左到右遍历数组，对于每个位置 $i$ ，如果 $i \geq k$ 且 $i - k$ 位置的元素为 $- 1$ ，那么当前位置的翻转状态应该与前一个位置的翻转状态相反。即 $flipped = flipped \oplus 1$ 。如果当前位置的元素与当前位置的翻转状态相同，那么我们需要翻转当前位置，此时我们判断一下 $i + k$ 是否超出了数组的长度，如果超出了数组的长度，那么就无法完成目标，返回 $- 1$ 。否则我们将当前位置的翻转状态取反，同时将答案增加 $1$ ，并且将当前位置的元素设置为 $- 1$ 。

这样当我们处理完数组中的所有元素时，返回答案即可。

时间复杂度 $O (n)$ ，其中 $n$ 是数组 $n u m s$ 的长度。空间复杂度 $O (1)$ 。

func minKBitFlips(nums []int, k int) (ans int) {
	flipped := 0
	for i, x := range nums {
		if i >= k && nums[i-k] == -1 {
			flipped ^= 1
		}
		if flipped == x {
			if i+k > len(nums) {
				return -1
			}
			flipped ^= 1
			ans++
			nums[i] = -1
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1016. 子串能表示从 1 到 N 数字的二进制串

中等1 种解法

标签：位运算、哈希表、字符串、滑动窗口

题目、示例与约束

给定一个二进制字符串 s 和一个正整数 n，如果对于 [1, n] 范围内的每个整数，其二进制表示都是 s 的 子字符串 ，就返回 true，否则返回 false 。

子字符串 是字符串中连续的字符序列。

示例 1：

输入：s = "0110", n = 3
输出：true

示例 2：

输入：s = "0110", n = 4
输出：false

提示：

1 <= s.length <= 1000
s[i] 不是 '0' 就是 '1'
1 <= n <= 10⁹

方法一：脑筋急转弯 · Go 实现

思考

$n$ 可达 $10^{9}$ ，逐个检查 $[1, n]$ 的二进制是否为 $s$ 的子串不可行。 $s$ 长度至多 $1000$ ，它能提供的互异子串远少于 $10^{9}$ ，故 $n > 1000$ 时可直接判否。

若整数 $x$ 的二进制出现在 $s$ 中，则 $⌊ x / 2 ⌋$ 相当于去掉最低位，也一定作为子串出现。因此只需验证较大的一半，即 $[⌊ n / 2 ⌋ + 1, n]$ 。

在 $n \leq 1000$ 的前提下对这些值调用子串查找即可。

我们注意到，字符串 $s$ 的长度不超过 $1000$ ，所以字符串 $s$ 能表示不超过 $1000$ 个二进制整数，因此，如果 $n > 1000$ ，那么 $s$ 肯定不能表示 $[1, . . n]$ 范围内的所有整数的二进制表示。

另外，对于一个整数 $x$ ，如果 $x$ 的二进制表示是 $s$ 的子串，那么 $⌊ x / 2 ⌋$ 的二进制表示也是 $s$ 的子串。因此，我们只需要判断 $[⌊ n / 2 ⌋ + 1, . . n]$ 范围内的整数的二进制表示是否是 $s$ 的子串即可。

时间复杂度 $O (m^{2} \times \log m)$ ，空间复杂度 $O (\log n)$ ，其中 $m$ 是字符串 $s$ 的长度，而 $n$ 为题目给定的正整数。

func queryString(s string, n int) bool {
	if n > 1000 {
		return false
	}
	for i := n; i > n/2; i-- {
		if !strings.Contains(s, strconv.FormatInt(int64(i), 2)) {
			return false
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

1040. 移动石子直到连续 II

中等1 种解法

标签：数组、数学、排序、滑动窗口

题目、示例与约束

在 X 轴上有一些不同位置的石子。给定一个整数数组 stones 表示石子的位置。

如果一个石子在最小或最大的位置，称其为 端点石子。每个回合，你可以将一颗 端点石子 拿起并移动到一个未占用的位置，使得该石子不再是一颗 端点石子。

值得注意的是，如果石子像 stones = [1,2,5] 这样，你将无法移动位于位置 5 的端点石子，因为无论将它移动到任何位置（例如 0 或 3），该石子都仍然会是端点石子。

当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。

以长度为 2 的数组形式返回答案，其中：

answer[0] 是你可以移动的最小次数
answer[1] 是你可以移动的最大次数。

示例 1：

输入：[7,4,9]
输出：[1,2]
解释：
我们可以移动一次，4 -> 8，游戏结束。
或者，我们可以移动两次 9 -> 5，4 -> 6，游戏结束。

示例 2：

输入：[6,5,4,3,10]
输出：[2,3]
解释：
我们可以移动 3 -> 8，接着是 10 -> 7，游戏结束。
或者，我们可以移动 3 -> 7, 4 -> 8, 5 -> 9，游戏结束。
注意，我们无法进行 10 -> 2 这样的移动来结束游戏，因为这是不合要求的移动。

提示：

3 <= stones.length <= 10⁴
1 <= stones[i] <= 10⁹
stones 的值各不相同。

方法一：排序 + 分类讨论 + 双指针 · Go 实现

思考

每次只能移动端点石子到非端点空位， $n \leq 10^{4}$ 且坐标达 $10^{9}$ ，不能逐步模拟。最大步数来自「尽量不填中间、每次只挪一格」；最小步数则是用尽量少的移动把石子装进某个长为 $n$ 的窗口。

排序后，第一次若动左端则跳过 $s t o n e s [0]$ 到 $s t o n e s [1]$ 的空隙，最多 $s t o n e s [n - 1] - s t o n e s [1] + 1 - (n - 1)$ 步，对称地动右端；二者取大。最小步用双指针找含 $n$ 个位置的窗口里已有石子数，缺口即需移动次数；特判「差一个且窗口几乎连满」时必须挪两次。

一次排序加一次滑动窗口同时得到 $[mi, mx]$ 。

我们先对数组 stones 进行升序排序，接下来分别考虑最大移动次数 $m x$ 和最小移动次数 $m i$ 。

对于最大移动次数 $m x$ ：

由于我们每一次只能选择将端点石子移动到未占用且不是端点石子的位置，如果我们选择 stones[0] 作为第一次移动的端点石子，那么从 stones[0] 到 stones[1] 之间的所有未占用的位置都会被跳过，我们可以选择移动到最近的且未占用的位置，接下来每一次都将最左端的石子移动到最近的且未占用的位置，那么最多可以移动的次数为 $s t o n e s [n - 1] - s t o n e s [1] + 1 - (n - 1)$ ；同理，如果我们选择 stones[n - 1] 作为第一次移动的端点石子，那么最多可以移动的次数为 $s t o n e s [n - 2] - s t o n e s [0] + 1 - (n - 1)$ 。取两者的最大值即为最大移动次数 $m x$ 。

对于最小移动次数 $m i$ ：

我们用双指针 $i$ 和 $j$ 标识一个窗口的左右端点，若窗口内的位置数 $s t o n e s [j] - s t o n e s [i] + 1 > n$ 时，我们需要缩小窗口，即指针 $i$ 向右移动。如果此时窗口中有连续的 $n - 1$ 个石子，即满足 $j - i + 1 = n - 1$ 且 $s t o n e s [j] - s t o n e s [i] + 1 = n - 1$ ，那么最少需要移动的次数为 $2$ ；否则，我们用 $n$ 减去窗口内的石子数，可以得到最少需要移动的次数，即 $n - (j - i + 1)$ 。取所有情况的最小值即为最小移动次数 $m i$ 。

时间复杂度 $O (n \times \log n)$ ，空间复杂度 $O (\log n)$ 。其中 $n$ 为数组 stones 的长度。

func numMovesStonesII(stones []int) []int {
	sort.Ints(stones)
	n := len(stones)
	mi := n
	mx := max(stones[n-1]-stones[1]+1, stones[n-2]-stones[0]+1) - (n - 1)
	i := 0
	for j, x := range stones {
		for x-stones[i]+1 > n {
			i++
		}
		if j-i+1 == n-1 && stones[j]-stones[i] == n-2 {
			mi = min(mi, 2)
		} else {
			mi = min(mi, n-(j-i+1))
		}
	}
	return []int{mi, mx}
}

力扣原题 · Doocs 题解来源

1052. 爱生气的书店老板

中等1 种解法

标签：数组、滑动窗口

题目、示例与约束

有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客在第 i 分钟结束后离开。

在某些分钟内，书店老板会生气。如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。

当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。

书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。

请你返回 这一天营业下来，最多有多少客户能够感到满意 。

示例 1：

输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
输出：16
解释：书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

示例 2：

输入：customers = [1], grumpy = [0], minutes = 1
输出：1

提示：

n == customers.length == grumpy.length
1 <= minutes <= n <= 2 * 10⁴
0 <= customers[i] <= 1000
grumpy[i] == 0 or 1

方法一：滑动窗口 · Go 实现

思考

不生气的顾客始终计入；技巧只能覆盖连续 $minutes$ 分钟的生气顾客。 $n \leq 2 \times 10^{4}$ ，应一次扫清所有窗口。

先把不生气时段的客流求和，再在生气客流上维护长为 $minutes$ 的滑动窗口最大值。

窗口右移时加上新分钟的 $c u s t o m e r s [i] \cdot g r u m p y [i]$ 、减去滑出的对应项，答案为固定客流加上该最大值。

根据题目描述，我们只需要统计老板不生气时的客户数量 $t o t$ ，再加上一个大小为 minutes 的滑动窗口中，老板生气时的客户数量的最大值 $m x$ 即可。

我们定义一个变量 $c n t$ 来记录滑动窗口中老板生气时的客户数量，初始值为前 minutes 分钟老板生气时的客户数量。然后我们遍历数组，每次移动滑动窗口时，更新 $c n t$ 的值，同时更新 $m x$ 的值。

最后返回 $t o t + m x$ 即可。

时间复杂度 $O (n)$ ，其中 $n$ 为数组 customers 的长度。空间复杂度 $O (1)$ 。

func maxSatisfied(customers []int, grumpy []int, minutes int) int {
	var cnt, tot int
	for i, c := range customers[:minutes] {
		cnt += c * grumpy[i]
		tot += c * (grumpy[i] ^ 1)
	}
	mx := cnt
	for i := minutes; i < len(customers); i++ {
		cnt += customers[i] * grumpy[i]
		cnt -= customers[i-minutes] * grumpy[i-minutes]
		mx = max(mx, cnt)
		tot += customers[i] * (grumpy[i] ^ 1)
	}
	return tot + mx
}

力扣原题 · Doocs 题解来源

1100. 长度为 K 的无重复字符子串 🔒

中等1 种解法

标签：哈希表、字符串、滑动窗口

题目、示例与约束

给你一个字符串 s，找出所有长度为 k 且不含重复字符的子串，请你返回全部满足要求的子串的数目。

示例 1：

输入：s = "havefunonleetcode", k = 5
输出：6
解释：
这里有 6 个满足题意的子串，分别是：'havef','avefu','vefun','efuno','etcod','tcode'。

示例 2：

输入：s = "home", k = 5
输出：0
解释：
注意：k 可能会大于 s 的长度。在这种情况下，就无法找到任何长度为 k 的子串。

提示：

1 <= s.length <= 10⁴
s 中的所有字符均为小写英文字母
1 <= k <= 10⁴

方法一：滑动窗口 + 哈希表 · Go 实现

思考

若枚举每个长度为 $k$ 的子串再扫描一遍判断字符是否互异，时间约为 $O (n k)$ 。在 $n, k \leq 10^{4}$ 时尚可接受，但相邻子串仅相差一头一尾两个字符，重复扫描没有必要。

为此维护长度为 $k$ 的窗口，并用哈希表记录窗内各字符频次：右端字符入窗、左端字符出窗，频次降为零则删键。表中键的个数恰为 $k$ ，当且仅当窗口内每个字符出现一次，据此累加答案。

我们维护一个长度为 $k$ 的滑动窗口，用一个哈希表 $c n t$ 统计窗口中每个字符的出现次数。

首先，我们将字符串 $s$ 的前 $k$ 个字符加入哈希表 $c n t$ 中，并判断 $c n t$ 的大小是否等于 $k$ ，如果等于 $k$ ，则说明窗口中的字符都不相同，答案 $a n s$ 加一。

接下来，我们从 $k$ 开始遍历字符串 $s$ ，每次将 $s [i]$ 加入哈希表 $c n t$ 中，同时将 $s [i - k]$ 从哈希表 $c n t$ 中减一，如果 $c n t [s [i - k]]$ 减一后等于 $0$ ，则将 $s [i - k]$ 从哈希表 $c n t$ 中删除。如果此时哈希表 $c n t$ 的大小等于 $k$ ，则说明窗口中的字符都不相同，答案 $a n s$ 加一。

最后，返回答案 $a n s$ 即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (min (k, | Σ |))$ ，其中 $n$ 为字符串 $s$ 的长度；而 $Σ$ 为字符集，本题中字符集为小写英文字母，所以 $| Σ | = 26$ 。

func numKLenSubstrNoRepeats(s string, k int) (ans int) {
	n := len(s)
	if n < k {
		return
	}
	cnt := map[byte]int{}
	for i := 0; i < k; i++ {
		cnt[s[i]]++
	}
	if len(cnt) == k {
		ans++
	}
	for i := k; i < n; i++ {
		cnt[s[i]]++
		cnt[s[i-k]]--
		if cnt[s[i-k]] == 0 {
			delete(cnt, s[i-k])
		}
		if len(cnt) == k {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1151. 最少交换次数来组合所有的 1 🔒

中等1 种解法

标签：数组、滑动窗口

题目、示例与约束

给出一个二进制数组 data，你需要通过交换位置，将数组中 任何位置 上的 1 组合到一起，并返回所有可能中所需 最少的交换次数。

示例 1:

输入: data = [1,0,1,0,1]
输出: 1
解释: 
有三种可能的方法可以把所有的 1 组合在一起：
[1,1,1,0,0]，交换 1 次；
[0,1,1,1,0]，交换 2 次；
[0,0,1,1,1]，交换 1 次。
所以最少的交换次数为 1。

示例 2:

输入：data = [0,0,0,1,0]
输出：0
解释： 
由于数组中只有一个 1，所以不需要交换。

示例 3:

输入：data = [1,0,1,0,1,0,0,1,1,0,1]
输出：3
解释：
交换 3 次，一种可行的只用 3 次交换的解决方案是 [0,0,0,0,0,1,1,1,1,1,1]。

示例 4:

输入: data = [1,0,1,0,1,0,1,1,1,0,1,0,0,1,1,1,0,0,1,1,1,0,1,0,1,1,0,0,0,1,1,1,1,0,0,1]
输出: 8

提示:

1 <= data.length <= 10⁵
data[i] == 0 or 1.

方法一：滑动窗口 · Go 实现

思考

全部 $1$ 最终要落入某一长度为 $k$ 的窗口， $k$ 为数组中 $1$ 的个数。窗口内 $0$ 的个数即需交换进来的 $1$ 的个数，等价于 $k$ 减窗口内 $1$ 的个数。滑动统计最大窗内 $1$ 数，答案为 $k$ 减该最大值。

我们先统计数组中 $1$ 的个数，记为 $k$ 。然后我们使用滑动窗口，窗口大小为 $k$ ，窗口右边界从左向右移动，统计窗口内 $1$ 的个数，记为 $t$ 。每次移动窗口时，都更新 $t$ 的值，最后窗口右边界移动到数组末尾时，窗口内 $1$ 的个数最多，记为 $m x$ 。最后答案为 $k - m x$ 。

时间复杂度 $O (n)$ ，其中 $n$ 为数组长度。空间复杂度 $O (1)$ 。

func minSwaps(data []int) int {
	k := 0
	for _, v := range data {
		k += v
	}
	t := 0
	for _, v := range data[:k] {
		t += v
	}
	mx := t
	for i := k; i < len(data); i++ {
		t += data[i]
		t -= data[i-k]
		mx = max(mx, t)
	}
	return k - mx
}

力扣原题 · Doocs 题解来源

1156. 单字符重复子串的最大长度

中等1 种解法

标签：哈希表、字符串、滑动窗口

题目、示例与约束

如果字符串中的所有字符都相同，那么这个字符串是单字符重复的字符串。

给你一个字符串 text，你只能交换其中两个字符一次或者什么都不做，然后得到一些单字符重复的子串。返回其中最长的子串的长度。

示例 1：

输入：text = "ababa"
输出：3

示例 2：

输入：text = "aaabaaa"
输出：6

示例 3：

输入：text = "aaabbaaa"
输出：4

示例 4：

输入：text = "aaaaa"
输出：5

示例 5：

输入：text = "abcdef"
输出：1

提示：

1 <= text.length <= 20000
text 仅由小写英文字母组成。

方法一：双指针 · Go 实现

思考

至多交换一次，最长单字符段要么是一段连续相同字符再并入一个远处的相同字符，要么是被一个不同字符隔开的两段相同字符拼起来。双指针切出每段长度 $l$ ，再看间隔一个字符后的同字符段 $r$ ，候选长度为 $min (l + r + 1, 该字符全局次数)$ ，避免无字符可换入。

我们先用哈希表或数组 $c n t$ 统计字符串 $t e x t$ 中每个字符出现的次数。

接下来，我们定义一个指针 $i$ ，初始时 $i = 0$ 。每一次，我们将指针 $j$ 指向 $i$ ，并不断地向右移动 $j$ ，直到 $j$ 指向的字符与 $i$ 指向的字符不同，此时我们得到了一个长度为 $l = j - i$ 的子串 $t e x t [i . . j - 1]$ ，其中所有字符都相同。

然后我们跳过指针 $j$ 指向的字符，用指针 $k$ 继续向右移动，直到 $k$ 指向的字符与 $i$ 指向的字符不同，此时我们得到了一个长度为 $r = k - j - 1$ 的子串 $t e x t [j + 1. . k - 1]$ ，其中所有字符都相同。那么我们最多通过一次交换操作，可以得到的最长单字符重复子串的长度为 $min (l + r + 1, c n t [t e x t [i]])$ 。接下来，我们将指针 $i$ 移动到 $j$ ，继续寻找下一个子串。我们取所有满足条件的子串的最大长度即可。

时间复杂度为 $O (n)$ ，空间复杂度 $O (C)$ 。其中 $n$ 为字符串的长度；而 $C$ 为字符集的大小，本题中 $C = 26$ 。

func maxRepOpt1(text string) (ans int) {
	cnt := [26]int{}
	for _, c := range text {
		cnt[c-'a']++
	}
	n := len(text)
	for i, j := 0, 0; i < n; i = j {
		j = i
		for j < n && text[j] == text[i] {
			j++
		}
		l := j - i
		k := j + 1
		for k < n && text[k] == text[i] {
			k++
		}
		r := k - j - 1
		ans = max(ans, min(l+r+1, cnt[text[i]-'a']))
	}
	return
}

力扣原题 · Doocs 题解来源

1176. 健身计划评估 🔒

简单2 种解法

标签：数组、滑动窗口

题目、示例与约束

一个节食者在第 i 天消耗 calories[i] 卡路里。

给定一个整数 k，对于每个连续的 k 天序列（对于所有的 0 <= i <= n-k，有 calories[i], calories[i+1], ..., calories[i+k-1]），他们想要知道 T，即在这 k 天序列期间消耗的总卡路里（calories[i] + calories[i+1] + ... + calories[i+k-1]）：

如果 T < lower，那么这份计划相对糟糕，并失去 1 分；
如果 T > upper，那么这份计划相对优秀，并获得 1 分；
否则，这份计划普普通通，分值不做变动。

请返回统计完所有 calories.length 天后得到的总分作为评估结果。

注意：总分可能是负数。

示例 1：

输入：calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3
输出：0
解释：calories[0], calories[1] < lower 而 calories[3], calories[4] > upper, 总分 = 0.

示例 2：

输入：calories = [3,2], k = 2, lower = 0, upper = 1
输出：1
解释：calories[0] + calories[1] > upper, 总分 = 1.

示例 3：

输入：calories = [6,5,0,0], k = 2, lower = 1, upper = 5
输出：0
解释：calories[0] + calories[1] > upper, calories[2] + calories[3] < lower, 总分 = 0.

提示：

1 <= k <= calories.length <= 10^5
0 <= calories[i] <= 20000
0 <= lower <= upper

方法一：前缀和 · Go 实现

思考

连续 $k$ 天热量与上下界比较后加减分。前缀和使任意窗口和 $s [i + k] - s [i]$ 为 $O (1)$ ，枚举起点即可。

我们先预处理出长度为 $n + 1$ 的前缀和数组 $s$ ，其中 $s [i]$ 表示前 $i$ 天的卡路里总和。

然后遍历前缀和数组 $s$ ，对于每个位置 $i$ ，计算 $s [i + k] - s [i]$ ，即为第 $i$ 天开始的连续 $k$ 天的卡路里总和。根据题意，对于每个 $s [i + k] - s [i]$ ，判断值与 $l o w e r$ 和 $u p p e r$ 的关系，更新答案即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为数组 calories 的长度。

func dietPlanPerformance(calories []int, k int, lower int, upper int) (ans int) {
	n := len(calories)
	s := make([]int, n+1)
	for i, x := range calories {
		s[i+1] = s[i] + x
	}
	for i := 0; i < n-k+1; i++ {
		t := s[i+k] - s[i]
		if t < lower {
			ans--
		} else if t > upper {
			ans++
		}
	}
	return
}

方法二：滑动窗口 · Go 实现

思考

方法一额外使用 $O (n)$ 前缀数组。定长窗口只需维护当前和：右端加入、左端减去，空间降为常数，判定规则不变。

我们维护一个长度为 $k$ 的滑动窗口，窗口内元素之和记为 $s$ 。如果 $s < l o w e r$ ，则分数减 $1$ ；如果 $ s \gt upper$，则分数加 $1$ 。

时间复杂度 $O (n)$ ，其中 $n$ 为数组 calories 的长度。空间复杂度 $O (1)$ 。

func dietPlanPerformance(calories []int, k int, lower int, upper int) (ans int) {
	n := len(calories)
	s := 0
	for _, x := range calories[:k] {
		s += x
	}
	if s < lower {
		ans--
	} else if s > upper {
		ans++
	}
	for i := k; i < n; i++ {
		s += calories[i] - calories[i-k]
		if s < lower {
			ans--
		} else if s > upper {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1234. 替换子串得到平衡字符串

中等1 种解法

标签：字符串、滑动窗口

题目、示例与约束

有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。

假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。

给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。

你可以用和「待替换子串」长度相同的任何其他字符串来完成替换。

请返回待替换子串的最小可能长度。

如果原字符串自身就是一个平衡字符串，则返回 0。

示例 1：

输入：s = "QWER"
输出：0
解释：s 已经是平衡的了。

示例 2：

输入：s = "QQWE"
输出：1
解释：我们需要把一个 'Q' 替换成 'R'，这样得到的 "RQWE" (或 "QRWE") 是平衡的。

示例 3：

输入：s = "QQQW"
输出：2
解释：我们可以把前面的 "QQ" 替换成 "ER"。

示例 4：

输入：s = "QQQQ"
输出：3
解释：我们可以替换后 3 个 'Q'，使 s = "QWER"。

提示：

1 <= s.length <= 10^5
s.length 是 4 的倍数
s 中只含有 'Q', 'W', 'E', 'R' 四种字符

方法一：计数 + 双指针 · Go 实现

思考

平衡要求四种字符各占 $n / 4$ 。 $n \leq 10^{5}$ ，不能枚举被替换子串。窗外四种计数都不超过 $n / 4$ 当且仅当该窗口覆盖了全部超额字符，且窗口越长越容易满足，具有单调性。

先统计全串频次；已平衡则答案为 $0$ 。否则右端吞入字符（窗外计数减一），当窗外均合法时收缩左端并更新最短窗口。双指针维护「窗外已平衡」的最短覆盖。

我们先用一个哈希表或数组 cnt 统计字符串 $s$ 中每个字符的数量，如果所有字符的数量都不超过 $n / 4$ ，那么字符串 $s$ 就是平衡字符串，直接返回 $0$ 。

否则，我们使用双指针 $j$ 和 $i$ 分别维护窗口的左右边界，初始时 $j = 0$ 。

接下来，从左到右遍历字符串 $s$ ，每次遍历到一个字符，就将该字符的数量减 $1$ ，然后判断当前窗口是否满足条件，即窗口外的字符数量都不超过 $n / 4$ 。如果满足条件，那么就更新答案，然后将窗口的左边界右移，直到不满足条件为止。

最后，返回答案即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (C)$ 。其中 $n$ 是字符串 $s$ 的长度；而 $C$ 是字符集的大小，本题中 $C = 4$ 。

func balancedString(s string) int {
	cnt := [4]int{}
	t := "QWER"
	n := len(s)
	for i := range s {
		cnt[strings.IndexByte(t, s[i])]++
	}
	m := n / 4
	if cnt[0] == m && cnt[1] == m && cnt[2] == m && cnt[3] == m {
		return 0
	}
	ans := n
	for i, j := 0, 0; i < n; i++ {
		cnt[strings.IndexByte(t, s[i])]--
		for j <= i && cnt[0] <= m && cnt[1] <= m && cnt[2] <= m && cnt[3] <= m {
			ans = min(ans, i-j+1)
			cnt[strings.IndexByte(t, s[j])]++
			j++
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1248. 统计「优美子数组」

中等1 种解法

标签：数组、哈希表、数学、前缀和、滑动窗口

题目、示例与约束

给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。

请返回这个数组中 「优美子数组」 的数目。

示例 1：

输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。

示例 2：

输入：nums = [2,4,6], k = 1
输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。

示例 3：

输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：16

提示：

1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length

方法一：前缀和 + 数组或哈希表 · Go 实现

思考

恰好 $k$ 个奇数的子数组， $n \leq 5 \times 10^{4}$ 。奇数看成 $1$ 、偶数看成 $0$ 后，即前缀和之差为 $k$ 的区间个数。

扫描时维护奇数个数 $t$ ，用计数器查已出现的 $t - k$ 次，再登记当前 $t$ 。前缀和把「恰好 $k$ 个奇数」变成哈希表上的一次查询。

题目求子数组中恰好有 $k$ 个奇数的子数组个数，我们可以求出每个前缀数组中奇数的个数 $t$ ，记录在数组或哈希表 $c n t$ 中。对于每个前缀数组，我们只需要求出前缀数组中奇数个数为 $t - k$ 的前缀数组个数，即为以当前前缀数组结尾的子数组个数。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为数组 $n u m s$ 的长度。

func numberOfSubarrays(nums []int, k int) (ans int) {
	n := len(nums)
	cnt := make([]int, n+1)
	cnt[0] = 1
	t := 0
	for _, v := range nums {
		t += v & 1
		if t >= k {
			ans += cnt[t-k]
		}
		cnt[t]++
	}
	return
}

力扣原题 · Doocs 题解来源

1297. 子串的最大出现次数

中等2 种解法

标签：哈希表、字符串、滑动窗口

题目、示例与约束

给你一个字符串 s ，请你返回满足以下条件且出现次数最大的任意子串的出现次数：

子串中不同字母的数目必须小于等于 maxLetters 。
子串的长度必须大于等于 minSize 且小于等于 maxSize 。

示例 1：

输入：s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
输出：2
解释：子串 "aab" 在原字符串中出现了 2 次。
它满足所有的要求：2 个不同的字母，长度为 3 （在 minSize 和 maxSize 范围内）。

示例 2：

输入：s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
输出：2
解释：子串 "aaa" 在原字符串中出现了 2 次，且它们有重叠部分。

示例 3：

输入：s = "aabcabcab", maxLetters = 2, minSize = 2, maxSize = 3
输出：3

示例 4：

输入：s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3
输出：0

提示：

1 <= s.length <= 10^5
1 <= maxLetters <= 26
1 <= minSize <= maxSize <= min(26, s.length)
s 只包含小写英文字母。

方法一：哈希表 + 枚举 · Go 实现

思考

满足字母种类与长度约束的子串中，出现次数最大者。更长的合法串若出现 $t$ 次，其长度为 $m i n S i z e$ 的前缀也至少出现 $t$ 次，故只需统计长度为 $m i n S i z e$ 且字母种类不超过 $m a x L e t t e r s$ 的子串。

$n \leq 10^{5}$ 、 $m i n S i z e \leq 26$ ，枚举所有该长窗口并用集合判种类，哈希表计数取最大。

根据题目描述，如果一个长串满足条件，那么这个长串的长度为 $minSize$ 的子串也一定满足条件。因此，我们只需要枚举 $s$ 中所有长度为 $minSize$ 的子串，然后利用哈希表记录所有子串的出现次数，找出最大的次数作为答案即可。

时间复杂度 $O (n \times m)$ ，空间复杂度 $O (n \times m)$ 。其中 $n$ 和 $m$ 分别为字符串 $s$ 的长度以及 $minSize$ 的大小。本题中 $m$ 不超过 $26$ 。

func maxFreq(s string, maxLetters int, minSize int, maxSize int) (ans int) {
	cnt := map[string]int{}
	for i := 0; i < len(s)-minSize+1; i++ {
		t := s[i : i+minSize]
		ss := map[rune]bool{}
		for _, c := range t {
			ss[c] = true
		}
		if len(ss) <= maxLetters {
			cnt[t]++
			if ans < cnt[t] {
				ans = cnt[t]
			}
		}
	}
	return
}

方法二：滑动窗口 + 字符串哈希 · Go 实现

思考

方法一以字符串为键，每窗口 $O (m i n S i z e)$ 建串。滑动窗口维护种类数，字符串哈希使子串键变成 $O (1)$ 整数，总时间线性。

我们可以使用滑动窗口来维护当前子串中不同字母的数目，同时使用字符串哈希来高效地计算子串的哈希值，从而避免使用字符串作为哈希表的键，提升性能。

具体地，我们定义一个 $Hashing$ 类来预处理字符串 $s$ 的前缀哈希值和幂次值，从而可以在 $O (1)$ 的时间内计算任意子串的哈希值。

然后，我们使用滑动窗口遍历字符串 $s$ ，维护当前窗口中不同字母的数目，并在窗口大小达到 $minSize$ 时，计算当前子串的哈希值并更新出现次数。然后，将窗口向右滑动一个位置，更新字母频率和不同字母数目。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为字符串 $s$ 的长度。

func maxFreq(s string, maxLetters int, minSize int, maxSize int) int {
	n := len(s)
	hashing := NewHashing(s)
	freq := make([]int, 256)
	k := 0
	ans := 0
	cnt := make(map[uint64]int)

	for i := 1; i <= n; i++ {
		c := s[i-1]
		freq[c]++
		if freq[c] == 1 {
			k++
		}

		if i >= minSize {
			if k <= maxLetters {
				x := hashing.Query(i-minSize+1, i)
				cnt[x]++
				if cnt[x] > ans {
					ans = cnt[x]
				}
			}
			j := i - minSize
			c2 := s[j]
			freq[c2]--
			if freq[c2] == 0 {
				k--
			}
		}
	}

	return ans
}

type Hashing struct {
	p, h []uint64
	mod  uint64
	base uint64
}

func NewHashing(word string) *Hashing {
	return NewHashingWithBase(word, 13331, 998244353)
}

func NewHashingWithBase(word string, base uint64, mod uint64) *Hashing {
	n := len(word)
	p := make([]uint64, n+1)
	h := make([]uint64, n+1)
	p[0] = 1
	for i := 1; i <= n; i++ {
		p[i] = p[i-1] * base % mod
		h[i] = (h[i-1]*base + uint64(word[i-1])) % mod
	}
	return &Hashing{p, h, mod, base}
}

func (hs *Hashing) Query(l, r int) uint64 {
	return (hs.h[r] + hs.mod - hs.h[l-1]*hs.p[r-l+1]%hs.mod) % hs.mod
}

力扣原题 · Doocs 题解来源

LeetCode Go · 滑动窗口（1） ​

3. 无重复字符的最长子串 ​

30. 串联所有单词的子串 ​

76. 最小覆盖子串 ​

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

187. 重复的DNA序列 ​

219. 存在重复元素 II ​

220. 存在重复元素 III ​

239. 滑动窗口最大值 ​

340. 至多包含 K 个不同字符的最长子串 🔒 ​

395. 至少有 K 个重复字符的最长子串 ​

424. 替换后的最长重复字符 ​

438. 找到字符串中所有字母异位词 ​

480. 滑动窗口中位数 ​

567. 字符串的排列 ​

594. 最长和谐子序列 ​

643. 子数组最大平均数 I ​

904. 水果成篮 ​

930. 和相同的二元子数组 ​

992. K 个不同整数的子数组 ​

995. K 连续位的最小翻转次数 ​

1016. 子串能表示从 1 到 N 数字的二进制串 ​

1040. 移动石子直到连续 II ​

1052. 爱生气的书店老板 ​

1100. 长度为 K 的无重复字符子串 🔒 ​

1151. 最少交换次数来组合所有的 1 🔒 ​

1156. 单字符重复子串的最大长度 ​

1176. 健身计划评估 🔒 ​

1234. 替换子串得到平衡字符串 ​

1248. 统计「优美子数组」 ​

1297. 子串的最大出现次数 ​

继续阅读

LeetCode Go · 滑动窗口（1）

3. 无重复字符的最长子串

30. 串联所有单词的子串

76. 最小覆盖子串

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

187. 重复的DNA序列

219. 存在重复元素 II

220. 存在重复元素 III

239. 滑动窗口最大值

340. 至多包含 K 个不同字符的最长子串 🔒

395. 至少有 K 个重复字符的最长子串

424. 替换后的最长重复字符

438. 找到字符串中所有字母异位词

480. 滑动窗口中位数

567. 字符串的排列

594. 最长和谐子序列

643. 子数组最大平均数 I

904. 水果成篮

930. 和相同的二元子数组

992. K 个不同整数的子数组

995. K 连续位的最小翻转次数

1016. 子串能表示从 1 到 N 数字的二进制串

1040. 移动石子直到连续 II

1052. 爱生气的书店老板

1100. 长度为 K 的无重复字符子串 🔒

1151. 最少交换次数来组合所有的 1 🔒

1156. 单字符重复子串的最大长度

1176. 健身计划评估 🔒

1234. 替换子串得到平衡字符串

1248. 统计「优美子数组」

1297. 子串的最大出现次数