LeetCode Go · 滑动窗口（2）

来源与许可

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

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

1343. 大小为 K 且平均值大于等于阈值的子数组数目

中等1 种解法

标签：数组、滑动窗口

题目、示例与约束

给你一个整数数组 arr 和两个整数 k 和 threshold 。

请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。

示例 1：

输入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
输出：3
解释：子数组 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分别为 4，5 和 6 。其他长度为 3 的子数组的平均值都小于 4 （threshold 的值)。

示例 2：

输入：arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
输出：6
解释：前 6 个长度为 3 的子数组平均值都大于 5 。注意平均值不是整数。

提示：

1 <= arr.length <= 10⁵
1 <= arr[i] <= 10⁴
1 <= k <= arr.length
0 <= threshold <= 10⁴

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

思考

定长 $k$ 的子数组平均数 $\geq threshold$ 。 $n \leq 10^{5}$ ，不可每次重算窗口。平均数比较等价于窗口和与 $k \times threshold$ 比较。维护长为 $k$ 的滑动和，右进左出，线性统计达标窗口。

不妨将 threshold 乘以 $k$ ，这样我们就可以直接比较窗口内的和与 threshold 的大小关系。

我们维护一个长度为 $k$ 的滑动窗口，每次计算窗口内的和 $s$ ，如果 $s$ 大于等于 threshold，则答案加一。

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

func numOfSubarrays(arr []int, k int, threshold int) (ans int) {
	threshold *= k
	s := 0
	for _, x := range arr[:k] {
		s += x
	}
	if s >= threshold {
		ans++
	}
	for i := k; i < len(arr); i++ {
		s += arr[i] - arr[i-k]
		if s >= threshold {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1358. 包含所有三种字符的子字符串数目

中等2 种解法

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

题目、示例与约束

给你一个字符串 s ，它只包含三种字符 a, b 和 c 。

请你返回 a，b 和 c 都至少出现过一次的子字符串数目。

示例 1：

输入：s = "abcabc"
输出：10
解释：包含 a，b 和 c 各至少一次的子字符串为 "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" 和 "abc" (相同字符串算多次)。

示例 2：

输入：s = "aaacb"
输出：3
解释：包含 a，b 和 c 各至少一次的子字符串为 "aaacb", "aacb" 和 "acb" 。

示例 3：

输入：s = "abc"
输出：1

提示：

3 <= s.length <= 5 x 10⁴
s 只包含字符 'a'，'b' 和 'c' 。

方法一：一次遍历 · Go 实现

思考

统计同时含 $a, b, c$ 的子串个数。 $n \leq 5 \times 10^{4}$ ，枚举两端为平方级。以 $i$ 为右端时，左端只需落到三个字母最近出现位置的最小值（含）之前。维护三个字母的最后下标，每次加上 $min (d [a], d [b], d [c]) + 1$ 。

我们用一个长度为 $3$ 的数组 $d$ 记录三种字符最近一次出现的位置，初始时均为 $- 1$ 。

遍历字符串 $s$ ，对于当前位置 $i$ ，我们先更新 $d [s [i]] = i$ ，然后合法的字符串个数为 $min (d [0], d [1], d [2]) + 1$ ，累加到答案中。

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

func numberOfSubstrings(s string) (ans int) {
	d := [3]int{-1, -1, -1}
	for i, c := range s {
		d[c-'a'] = i
		ans += min(d[0], min(d[1], d[2])) + 1
	}
	return
}

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

思考

方法一依赖「最近出现」的闭式。也可用计数窗口：右端纳入后，当三种字母都出现时收缩左端，直到缺一种；此时以 $r$ 为右端的合法左端个数恰为当前的 $l$ 。两种线性写法，后者不显式存最后位置。

我们可以使用滑动窗口的方法求解。维护一个窗口 $[l, r]$ 和一个数组 $cnt$ 记录窗口内各字符的出现次数。

遍历字符串，不断右移右边界 $r$ ，将 $s [r]$ 加入窗口。若窗口内 $a$ 、 $b$ 、 $c$ 均至少出现一次，则不断右移左边界 $l$ ，直到窗口内不再同时包含三种字符为止。

此时，所有以 $r$ 为右端点且包含 $a$ 、 $b$ 、 $c$ 的子字符串的左端点可取 $0, 1, \dots, l - 1$ ，共 $l$ 个，累加到答案中。

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

func numberOfSubstrings(s string) int {
	ans, l := 0, 0
	cnt := [3]int{}

	for r := 0; r < len(s); r++ {
		cnt[s[r]-'a']++

		for cnt[0] > 0 && cnt[1] > 0 && cnt[2] > 0 {
			cnt[s[l]-'a']--
			l++
		}

		ans += l
	}

	return ans
}

力扣原题 · Doocs 题解来源

1423. 可获得的最大点数

中等1 种解法

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

题目、示例与约束

几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。

每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。

你的点数就是你拿到手中的所有卡牌的点数之和。

给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。

示例 1：

输入：cardPoints = [1,2,3,4,5,6,1], k = 3
输出：12
解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。

示例 2：

输入：cardPoints = [2,2,2], k = 2
输出：4
解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。

示例 3：

输入：cardPoints = [9,7,7,9,7,7,9], k = 7
输出：55
解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。

示例 4：

输入：cardPoints = [1,1000,1], k = 1
输出：1
解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。

示例 5：

输入：cardPoints = [1,79,80,1,1,1,200,1], k = 3
输出：202

提示：

1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length

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

思考

每次只能从两端取牌，共取 $k$ 张，等价于左边取 $i$ 张、右边取 $k - i$ 张。 $n \leq 10^{5}$ ，不能对每个 $i$ 重新求和。

先取右端 $k$ 张作为窗口，再依次用左端一张替换窗口最左的那张右端牌，线性更新和并取最大。

我们可以用一个长度为 $k$ 的滑动窗口来模拟这个过程。

初始时我们将窗口放在数组的末尾，即索引为 $n - k$ 到索引 $n - 1$ 的这 $k$ 个位置，窗口内卡牌的点数之和记为 $s$ ，初始答案 $a n s$ 的值也为 $s$ 。这其实是从数组的开头拿走 $0$ 张卡牌的情况。

接下来，我们考虑从数组的开头依次拿 $1, 2, . . ., k$ 张卡牌的情况，假设取到的卡牌为 $c a r d P o i n t s [i]$ ，那么我们将其加入 $s$ ，由于窗口的长度限制为 $k$ ，我们需要将 $c a r d P o i n t s [n - k + i]$ 从 $s$ 中减去，这样我们就可以计算出拿到的 $k$ 张卡牌的点数之和，更新答案 $a n s$ 。

时间复杂度 $O (k)$ ，其中 $k$ 给题目中给出的整数。空间复杂度 $O (1)$ 。

func maxScore(cardPoints []int, k int) int {
	n := len(cardPoints)
	s := 0
	for _, x := range cardPoints[n-k:] {
		s += x
	}
	ans := s
	for i := 0; i < k; i++ {
		s += cardPoints[i] - cardPoints[n-k+i]
		ans = max(ans, s)
	}
	return ans
}

力扣原题 · Doocs 题解来源

1438. 绝对差不超过限制的最长连续子数组

中等3 种解法

标签：队列、数组、有序集合、滑动窗口、单调队列、堆（优先队列）

题目、示例与约束

给你一个整数数组 nums 和一个整数 limit。

请你返回 最长非空子数组 的长度，要求该 子数组 中 任意两个元素 之间的差的 绝对值 都 小于或等于 limit。

示例 1：

输入： nums = [8,2,4,7], limit = 4

输出： 2

解释：

检查所有子数组，计算每个子数组中任意两个元素之间的最大绝对差：
[8] 的最大绝对差为 |8-8| = 0 <= 4。
[8,2] 的最大绝对差为 |8-2| = 6 > 4。
[8,2,4] 的最大绝对差为 |8-2| = 6 > 4。
[8,2,4,7] 的最大绝对差为 |8-2| = 6 > 4。
[2] 的最大绝对差为 |2-2| = 0 <= 4。
[2,4] 的最大绝对差为 |4-2| = 2 <= 4。
[2,4,7] 的最大绝对差为 |7-2| = 5 > 4。注意，元素对 (2, 7) 并不相邻，但仍然需要进行比较。
[4] 的最大绝对差为 |4-4| = 0 <= 4。
[4,7] 的最大绝对差为 |7-4| = 3 <= 4。
[7] 的最大绝对差为 |7-7| = 0 <= 4。
因此，最长子数组的长度为 2。

示例 2：

输入： nums = [10,1,2,4,7,2], limit = 5

输出： 4

解释：

子数组 [2,4,7,2] 满足条件，因为其中任意两个元素之间的绝对差都不超过 5，最大绝对差为 |7-2| = 5。

该子数组无法向左扩展，因为 [1,2,4,7,2] 包含元素对 (1, 7)，其绝对差为 |7-1| = 6 > 5。因此，最长子数组的长度为 4。

示例 3：

输入： nums = [4,2,2,2,4,4,2,2], limit = 0

输出： 3

解释：

由于 limit = 0，子数组中任意两个元素都必须相等，因此只有由相同元素连续组成的子数组才满足条件。

满足条件的最长子数组为 [2,2,2]，长度为 3。

提示：

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

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

思考

子数组的最大最小之差随窗口变长而不减。 $n \leq 10^{5}$ ，枚举所有区间是 $O (n^{2})$ 。固定右端点，左端只需右移到窗口极值差不超过 $l i m i t$ 。

有序集合同时给出当前窗口的最小、最大值，超限则删除左端元素。最长合法窗口即答案。

我们可以枚举每个位置作为子数组的右端点，找到其对应的最靠左的左端点，满足区间内中最大值与最小值的差值不超过 $l i m i t$ 。过程中，我们用有序集合维护窗口内的最大值和最小值。

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

func longestSubarray(nums []int, limit int) (ans 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)
		}
	}
	st := redblacktree.New[int, int]()
	j := 0
	for i, x := range nums {
		merge(st, x, 1)
		for ; st.Right().Key-st.Left().Key > limit; j++ {
			merge(st, nums[j], -1)
		}
		ans = max(ans, i-j+1)
	}
	return
}

方法二：二分查找 + 滑动窗口 · Go 实现

思考

方法一对每个右端点动态收缩，长度本身具有单调性：若存在长为 $m i d$ 的合法段，则更短的也存在。可二分长度，再用两个单调队列检查是否有窗口满足差值约束。

时间仍为 $O (n \log n)$ ，把「求最长」改成了判定问题。

我们注意到，如果一个长度为 $k$ 的子数组满足条件，那么长度 $k^{'} < k$ 的子数组也满足条件，这存在着单调性，因此，我们可以使用二分查找，找到最长的满足条件的子数组。

我们定义二分查找的左边界 $l = 0$ ，右边界 $r = n$ 。对于每个 $m i d = \frac{l + r + 1}{2}$ ，我们检查是否存在一个长度为 $m i d$ 的子数组满足条件。如果存在，我们更新 $l = m i d$ ，否则更新 $r = m i d - 1$ 。那么问题转换为数组中是否存在一个长度为 $m i d$ 的子数组满足条件，这其实是求滑动窗口中的最大值和最小值的差值不超过 $l i m i t$ 。我们可以用两个单调队列分别维护窗口内的最大值和最小值。

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

func longestSubarray(nums []int, limit int) int {
	l, r := 0, len(nums)
	check := func(k int) bool {
		minq := Deque{}
		maxq := Deque{}
		for i, x := range nums {
			for !minq.Empty() && i-minq.Front()+1 > k {
				minq.PopFront()
			}
			for !maxq.Empty() && i-maxq.Front()+1 > k {
				maxq.PopFront()
			}
			for !minq.Empty() && nums[minq.Back()] >= x {
				minq.PopBack()
			}
			for !maxq.Empty() && nums[maxq.Back()] <= x {
				maxq.PopBack()
			}
			minq.PushBack(i)
			maxq.PushBack(i)
			if i >= k-1 && nums[maxq.Front()]-nums[minq.Front()] <= limit {
				return true
			}
		}
		return false
	}
	for l < r {
		mid := (l + r + 1) >> 1
		if check(mid) {
			l = mid
		} else {
			r = mid - 1
		}
	}
	return l
}

// template
type Deque struct{ l, r []int }

func (q Deque) Empty() bool {
	return len(q.l) == 0 && len(q.r) == 0
}

func (q Deque) Size() int {
	return len(q.l) + len(q.r)
}

func (q *Deque) PushFront(v int) {
	q.l = append(q.l, v)
}

func (q *Deque) PushBack(v int) {
	q.r = append(q.r, v)
}

func (q *Deque) PopFront() (v int) {
	if len(q.l) > 0 {
		q.l, v = q.l[:len(q.l)-1], q.l[len(q.l)-1]
	} else {
		v, q.r = q.r[0], q.r[1:]
	}
	return
}

func (q *Deque) PopBack() (v int) {
	if len(q.r) > 0 {
		q.r, v = q.r[:len(q.r)-1], q.r[len(q.r)-1]
	} else {
		v, q.l = q.l[0], q.l[1:]
	}
	return
}

func (q Deque) Front() int {
	if len(q.l) > 0 {
		return q.l[len(q.l)-1]
	}
	return q.r[0]
}

func (q Deque) Back() int {
	if len(q.r) > 0 {
		return q.r[len(q.r)-1]
	}
	return q.l[0]
}

func (q Deque) Get(i int) int {
	if i < len(q.l) {
		return q.l[len(q.l)-1-i]
	}
	return q.r[i-len(q.l)]
}

方法三：滑动窗口 + 双向队列 · Go 实现

思考

方法一、二都带对数因子。窗口最大、最小本身可用两个单调双端队列在摊还 $O (1)$ 内维护，右端扩张、左端在差值超限时收缩，总体线性。

我们可以使用双向队列维护窗口内的最大值和最小值。我们维护两个双向队列，分别存储窗口内的最大值和最小值的下标。定义两个指针 $l$ 和 $r$ 分别指向窗口的左边界和右边界。

每次向右移动右边界 $r$ ，判断最大值队列的队尾下标对应的元素是否小于当前元素，如果小于，则将队尾元素出队，直到最大值队列的队尾元素对应的元素不小于当前元素。同理，判断最小值队列的队尾下标对应的元素是否大于当前元素，如果大于，则将队尾元素出队，直到最小值队列的队尾元素对应的元素不大于当前元素。然后，将当前元素的下标入队。

如果最大值队列的队首元素和最小值队列的队首元素的差值大于 $l i m i t$ ，则向右移动左边界 $l$ ，然后如果最大值队列的队首元素小于 $l$ ，则将最大值队列的队首元素出队，如果最小值队列的队首元素小于 $l$ ，则将最小值队列的队首元素出队。

答案为 $n - l$ 。

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

func longestSubarray(nums []int, limit int) int {
	var maxq, minq Deque
	n := len(nums)
	l := 0
	for r, x := range nums {
		for !maxq.Empty() && nums[maxq.Back()] < x {
			maxq.PopBack()
		}
		for !minq.Empty() && nums[minq.Back()] > x {
			minq.PopBack()
		}
		maxq.PushBack(r)
		minq.PushBack(r)

		if nums[maxq.Front()]-nums[minq.Front()] > limit {
			l++
			if maxq.Front() < l {
				maxq.PopFront()
			}
			if minq.Front() < l {
				minq.PopFront()
			}
		}
	}
	return n - l
}

type Deque struct{ l, r []int }

func (q Deque) Empty() bool {
	return len(q.l) == 0 && len(q.r) == 0
}

func (q Deque) Size() int {
	return len(q.l) + len(q.r)
}

func (q *Deque) PushFront(v int) {
	q.l = append(q.l, v)
}

func (q *Deque) PushBack(v int) {
	q.r = append(q.r, v)
}

func (q *Deque) PopFront() (v int) {
	if len(q.l) > 0 {
		q.l, v = q.l[:len(q.l)-1], q.l[len(q.l)-1]
	} else {
		v, q.r = q.r[0], q.r[1:]
	}
	return
}

func (q *Deque) PopBack() (v int) {
	if len(q.r) > 0 {
		q.r, v = q.r[:len(q.r)-1], q.r[len(q.r)-1]
	} else {
		v, q.l = q.l[0], q.l[1:]
	}
	return
}

func (q Deque) Front() int {
	if len(q.l) > 0 {
		return q.l[len(q.l)-1]
	}
	return q.r[0]
}

func (q Deque) Back() int {
	if len(q.r) > 0 {
		return q.r[len(q.r)-1]
	}
	return q.l[0]
}

func (q Deque) Get(i int) int {
	if i < len(q.l) {
		return q.l[len(q.l)-1-i]
	}
	return q.r[i-len(q.l)]
}

力扣原题 · Doocs 题解来源

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

中等1 种解法

标签：字符串、滑动窗口

题目、示例与约束

给你字符串 s 和整数 k 。

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

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

示例 1：

输入：s = "abciiidef", k = 3
输出：3
解释：子字符串 "iii" 包含 3 个元音字母。

示例 2：

输入：s = "aeiou", k = 2
输出：2
解释：任意长度为 2 的子字符串都包含 2 个元音字母。

示例 3：

输入：s = "leetcode", k = 3
输出：2
解释："lee"、"eet" 和 "ode" 都包含 2 个元音字母。

示例 4：

输入：s = "rhythms", k = 4
输出：0
解释：字符串 s 中不含任何元音字母。

示例 5：

输入：s = "tryhard", k = 4
输出：1

提示：

1 <= s.length <= 10^5
s 由小写英文字母组成
1 <= k <= s.length

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

思考

定长 $k$ 的子串中元音最多。 $n \leq 10^{5}$ ，不能对每个起点重数。先统计前 $k$ 个，再滑窗加减进出字符是否为元音。

我们首先统计前 $k$ 个字符中元音字母的个数，记为 $c n t$ ，初始化答案 $a n s$ 为 $c n t$ 。

然后我们从 $k$ 开始遍历字符串，每次遍历时，我们将当前字符加入窗口，如果当前字符是元音字母，则 $c n t$ 加一；将窗口第一个字符移出窗口，如果移除的字符是元音字母，则 $c n t$ 减一。然后，我们更新答案 $a n s = max (a n s, c n t)$ 。

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

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

func maxVowels(s string, k int) int {
	isVowel := func(c byte) bool {
		return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
	}
	cnt := 0
	for i := 0; i < k; i++ {
		if isVowel(s[i]) {
			cnt++
		}
	}
	ans := cnt
	for i := k; i < len(s); i++ {
		if isVowel(s[i-k]) {
			cnt--
		}
		if isVowel(s[i]) {
			cnt++
		}
		ans = max(ans, cnt)
	}
	return ans
}

力扣原题 · Doocs 题解来源

1499. 满足不等式的最大值

困难2 种解法

标签：队列、数组、滑动窗口、单调队列、堆（优先队列）

题目、示例与约束

给你一个数组 points 和一个整数 k 。数组中每个元素都表示二维平面上的点的坐标，并按照横坐标 x 的值从小到大排序。也就是说 points[i] = [x_i, y_i] ，并且在 1 <= i < j <= points.length 的前提下， x_i < x_j 总成立。

请你找出 y_i + y_j + |x_i - x_j| 的 最大值，其中 |x_i - x_j| <= k 且 1 <= i < j <= points.length。

题目测试数据保证至少存在一对能够满足 |x_i - x_j| <= k 的点。

示例 1：

输入：points = [[1,3],[2,0],[5,10],[6,-10]], k = 1
输出：4
解释：前两个点满足 |x_i - x_j| <= 1 ，代入方程计算，则得到值 3 + 0 + |1 - 2| = 4 。第三个和第四个点也满足条件，得到值 10 + -10 + |5 - 6| = 1 。
没有其他满足条件的点，所以返回 4 和 1 中最大的那个。

示例 2：

输入：points = [[0,0],[3,0],[9,2]], k = 3
输出：3
解释：只有前两个点满足 |x_i - x_j| <= 3 ，代入方程后得到值 0 + 0 + |0 - 3| = 3 。

提示：

2 <= points.length <= 10⁵
points[i].length == 2
-10⁸ <= x_i, y_i <= 10⁸
0 <= k <= 2 * 10⁸
对于所有的 1 <= i < j <= points.length，均有 x_i < x_j。
x_i 构成一个严格递增序列。

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

思考

$x$ 严格递增， $n \leq 10^{5}$ ，枚举点对不可行。 $y_{i} + y_{j} + | x_{i} - x_{j} | = (y_{i} - x_{i}) + (x_{j} + y_{j})$ ，对当前 $j$ 只需窗口 $x_{j} - x_{i} \leq k$ 内最大的 $y_{i} - x_{i}$ 。

堆中存 $(x_{i} - y_{i}, x_{i})$ （最小堆即最大 $y - x$ ），弹出过期点后与当前 $x + y$ 相加。

题目要求 $y_{i} + y_{j} + | x_{i} - x_{j} |$ 的最大值，其中 $i < j$ ，并且 $| x_{i} - x_{j} | \leq k$ 。由于 $x_{i}$ 是严格单调递增的，那么：

\begin{aligned} y_{i} + y_{j} + | x_{i} - x_{j} | & = y_{i} + y_{j} + x_{j} - x_{i} \\ = (y_{i} - x_{i}) + (x_{j} + y_{j}) \end{aligned}

因此，对于当前遍历到的点 $(x_{j}, y_{j})$ ，我们只需要找到前面所有满足 $x_{j} - x_{i} \leq k$ 的点 $(x_{i}, y_{i})$ 中 $y_{i} - x_{i}$ 的最大值，再加上当前的 $x_{j} + y_{j}$ 即可。而 $y_{i} - x_{i}$ 的最大值，我们可以使用优先队列（大根堆）来维护。

具体地，我们定义一个优先队列（大根堆） $p q$ ，堆中每个元素是一个二元组 $(y_{i} - x_{i}, x_{i})$ 。

当我们遍历到点 $(x, y)$ 时，如果堆 $p q$ 不为空，并且 $x - p q [0] [1] > k$ ，那么循环将堆顶元素弹出，直到堆为空或者满足 $x - p q [0] [1] \leq k$ 。此时，堆顶元素 $(y_{i} - x_{i}, x_{i})$ 即为所有满足 $x_{j} - x_{i} \leq k$ 的点中 $y_{i} - x_{i}$ 的最大值，此时更新答案 $a n s = max (a n s, x + y + p q [0] [0])$ 。

然后，我们将点 $(x, y)$ 加入堆中，继续遍历下一个点，直到遍历完整个数组 $p o i n t s$ 。

时间复杂度 $O (n \times \log n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是数组 $p o i n t s$ 的长度。

func findMaxValueOfEquation(points [][]int, k int) int {
	ans := -(1 << 30)
	hp := hp{}
	for _, p := range points {
		x, y := p[0], p[1]
		for hp.Len() > 0 && x-hp[0].x > k {
			heap.Pop(&hp)
		}
		if hp.Len() > 0 {
			ans = max(ans, x+y+hp[0].v)
		}
		heap.Push(&hp, pair{y - x, x})
	}
	return ans
}

type pair struct{ v, x 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
}
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 实现

思考

方法一每次操作 $O (\log n)$ 。窗口内 $y - x$ 的最大值可用单调递减双端队列在摊还 $O (1)$ 内维护：过期弹队首，队尾不优于当前的弹出后再入队。

这道题实际上需要我们维护的是一个长度为 $k$ 的窗口中 $y - x$ 的最大值，单调队列可以很好地解决这个问题。

具体地，我们定义一个单调队列 $q$ ，队列中每个元素是一个二元组 $(x_{i}, y_{i})$ 。

当我们遍历到点 $(x, y)$ 时，如果队列 $q$ 不为空，并且 $x - q [0] [0] > k$ ，那么不断弹出队首元素，直到队列为空或者满足 $x - q [0] [0] \leq k$ 。此时，队首元素 $(x_{i}, y_{i})$ 即为所有满足 $x_{j} - x_{i} \leq k$ 的点中 $y_{i} - x_{i}$ 的最大值，此时更新答案 $a n s = max (a n s, x + y + y_{i} - x_{i})$ 。

接下来，在将点 $(x, y)$ 加入队尾之前，我们将队列中所有 $y_{i} - x_{i} \leq y - x$ 的元素 $(x_{i}, y_{i})$ 弹出队列，然后将点 $(x, y)$ 加入队尾。继续遍历下一个点，直到遍历完整个数组 $p o i n t s$ 。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是数组 $p o i n t s$ 的长度。

func findMaxValueOfEquation(points [][]int, k int) int {
	ans := -(1 << 30)
	q := [][2]int{}
	for _, p := range points {
		x, y := p[0], p[1]
		for len(q) > 0 && x-q[0][0] > k {
			q = q[1:]
		}
		if len(q) > 0 {
			ans = max(ans, x+y+q[0][1]-q[0][0])
		}
		for len(q) > 0 && y-x >= q[len(q)-1][1]-q[len(q)-1][0] {
			q = q[:len(q)-1]
		}
		q = append(q, [2]int{x, y})
	}
	return ans
}

力扣原题 · Doocs 题解来源

1610. 可见点的最大数目

困难1 种解法

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

题目、示例与约束

给你一个点数组 points 和一个表示角度的整数 angle ，你的位置是 location ，其中 location = [pos_x, pos_y] 且 points[i] = [x_i, y_i] 都表示 X-Y 平面上的整数坐标。

最开始，你面向东方进行观测。你不能进行移动改变位置，但可以通过自转调整观测角度。换句话说，pos_x 和 pos_y 不能改变。你的视野范围的角度用 angle 表示，这决定了你观测任意方向时可以多宽。设 d 为你逆时针自转旋转的度数，那么你的视野就是角度范围 [d - angle/2, d + angle/2] 所指示的那片区域。

Your browser does not support the video tag or this video format.

对于每个点，如果由该点、你的位置以及从你的位置直接向东的方向形成的角度 位于你的视野中 ，那么你就可以看到它。

同一个坐标上可以有多个点。你所在的位置也可能存在一些点，但不管你的怎么旋转，总是可以看到这些点。同时，点不会阻碍你看到其他点。

返回你能看到的点的最大数目。

示例 1：

输入：points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1]
输出：3
解释：阴影区域代表你的视野。在你的视野中，所有的点都清晰可见，尽管 [2,2] 和 [3,3]在同一条直线上，你仍然可以看到 [3,3] 。

示例 2：

输入：points = [[2,1],[2,2],[3,4],[1,1]], angle = 90, location = [1,1]
输出：4
解释：在你的视野中，所有的点都清晰可见，包括你所在位置的那个点。

示例 3：

输入：points = [[1,0],[2,1]], angle = 13, location = [1,1]
输出：1
解释：如图所示，你只能看到两点之一。

提示：

1 <= points.length <= 10⁵
points[i].length == 2
location.length == 2
0 <= angle < 360
0 <= pos_x, pos_y, x_i, y_i <= 100

方法一 · Go 实现

思考

视野是以自身为顶点、张角为 $angle$ 的扇形，点数可达 $10^{5}$ ，枚举每一对极角边界会超时。与位置重合的点对任意朝向均可见，应单独计入。

将其余点换成相对极角并排序后，可见集合对应长度为 $angle$ 的圆周窗口。将序列拼接一份加上 $2 π$ ，即可把环形窗口化为线性区间。

对每个左端点 $v [i]$ ，用二分查找不超过 $v [i] + θ$ 的最右位置，窗口点数取最大后再加上重合点数。

func visiblePoints(points [][]int, angle int, location []int) int {
	same := 0
	v := []float64{}
	for _, p := range points {
		if p[0] == location[0] && p[1] == location[1] {
			same++
		} else {
			v = append(v, math.Atan2(float64(p[1]-location[1]), float64(p[0]-location[0])))
		}
	}
	sort.Float64s(v)
	for _, deg := range v {
		v = append(v, deg+2*math.Pi)
	}

	mx := 0
	t := float64(angle) * math.Pi / 180
	for i, j := 0, 0; j < len(v); j++ {
		for i < j && v[j]-v[i] > t {
			i++
		}
		mx = max(mx, j-i+1)
	}
	return same + mx
}

力扣原题 · Doocs 题解来源

1652. 拆炸弹

简单2 种解法

标签：数组、滑动窗口

题目、示例与约束

你有一个炸弹需要拆除，时间紧迫！你的情报员会给你一个长度为 n 的循环数组 code 以及一个密钥 k 。

为了获得正确的密码，你需要替换掉每一个数字。所有数字会同时被替换。

如果 k > 0 ，将第 i 个数字用 接下来 k 个数字之和替换。
如果 k < 0 ，将第 i 个数字用之前 k 个数字之和替换。
如果 k == 0 ，将第 i 个数字用 0 替换。

由于 code 是循环的， code[n-1] 下一个元素是 code[0] ，且 code[0] 前一个元素是 code[n-1] 。

给你循环数组 code 和整数密钥 k ，请你返回解密后的结果来拆除炸弹！

示例 1：

输入：code = [5,7,1,4], k = 3
输出：[12,10,16,13]
解释：每个数字都被接下来 3 个数字之和替换。解密后的密码为 [7+1+4, 1+4+5, 4+5+7, 5+7+1]。注意到数组是循环连接的。

示例 2：

输入：code = [1,2,3,4], k = 0
输出：[0,0,0,0]
解释：当 k 为 0 时，所有数字都被 0 替换。

示例 3：

输入：code = [2,4,9,3], k = -2
输出：[12,5,6,13]
解释：解密后的密码为 [3+9, 2+3, 4+2, 9+4] 。注意到数组是循环连接的。如果 k 是负数，那么和为 之前 的数字。

提示：

n == code.length
1 <= n <= 100
1 <= code[i] <= 100
-(n - 1) <= k <= n - 1

方法一：模拟 · Go 实现

思考

环形数组上每个位置替换为后 $k$ 项或前 $| k |$ 项之和， $k = 0$ 则全零。 $n$ 与 $| k |$ 都很小，直接按定义累加即可。

下标对 $n$ 取模处理环；正 $k$ 扫 $[i + 1, i + k]$ ，负 $k$ 扫 $[i + k, i)$ 。

我们定义一个长度为 $n$ 的答案数组 $a n s$ ，初始时所有元素都为 $0$ 。根据题意，若 $k$ 为 $0$ ，直接返回 $a n s$ 。

否则，遍历每个位置 $i$ ：

若 $k$ 为正数，那么 $i$ 位置的值为 $i$ 位置后 $k$ 个位置的值之和，即：

a n s [i] = \sum_{j = i + 1}^{i + k} c o d e [j mod n]

若 $k$ 为负数，那么 $i$ 位置的值为 $i$ 位置前 $| k |$ 个位置的值之和，即：

a n s [i] = \sum_{j = i + k}^{i - 1} c o d e [(j + n) mod n]

时间复杂度 $O (n \times | k |)$ ，忽略答案的空间消耗，空间复杂度 $O (1)$ 。

func decrypt(code []int, k int) []int {
	n := len(code)
	ans := make([]int, n)
	if k == 0 {
		return ans
	}
	for i := 0; i < n; i++ {
		if k > 0 {
			for j := i + 1; j < i+k+1; j++ {
				ans[i] += code[j%n]
			}
		} else {
			for j := i + k; j < i; j++ {
				ans[i] += code[(j+n)%n]
			}
		}
	}
	return ans
}

方法二：前缀和 · Go 实现

思考

方法一对每个 $i$ 重复相加。把数组拼接一份求前缀和后，任意环形区间变成两次前缀相减，总时间 $O (n)$ 。

在方法一中，对于每个位置 $i$ ，都需要遍历 $k$ 个位置，有很多重复计算的操作。我们可以利用前缀和来优化。

我们将 code 数组复制一份（可以不用执行复制操作，直接通过循环遍历取模实现），得到两倍长度的数组，对其求前缀和，得到长度为 $2 \times n + 1$ 的前缀和数组 $s$ 。

若 $k$ 为正数，那么 $i$ 位置的值为 $i$ 位置后 $k$ 个位置的值之和，即 $a n s [i] = s [i + k + 1] - s [i + 1]$ 。

若 $k$ 为负数，那么 $i$ 位置的值为 $i$ 位置前 $| k |$ 个位置的值之和，即 $a n s [i] = s [i + n] - s [i + k + n]$ 。

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

func decrypt(code []int, k int) []int {
	n := len(code)
	ans := make([]int, n)
	if k == 0 {
		return ans
	}
	s := make([]int, n<<1|1)
	for i := 0; i < n<<1; i++ {
		s[i+1] = s[i] + code[i%n]
	}
	for i := range code {
		if k > 0 {
			ans[i] = s[i+k+1] - s[i+1]
		} else {
			ans[i] = s[i+n] - s[i+k+n]
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1695. 删除子数组的最大得分

中等2 种解法

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

题目、示例与约束

给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。删除子数组的得分就是子数组各元素之和。

返回 只删除一个 子数组可获得的 最大得分 。

如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是 a 的一个子数组。

示例 1：

输入：nums = [4,2,4,5,6]
输出：17
解释：最优子数组是 [2,4,5,6]

示例 2：

输入：nums = [5,2,1,2,5,2,1,2,5]
输出：8
解释：最优子数组是 [5,2,1] 或 [1,2,5]

提示：

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

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

思考

求元素互异的连续子数组的最大和。 $n$ 达 $10^{5}$ ，用上次出现位置把左端 $j$ 推到重复点之后，前缀和给出区间和。

数组 $d$ 记下每个值最近下标，扫到 $v$ 时 $j = max (j, d [v])$ ，用 $s [i] - s [j]$ 更新答案。

我们用数组或哈希表 $d$ 记录每个数字最后一次出现的位置，用前缀和数组 $s$ 记录从起点到当前位置的和。我们用变量 $j$ 记录当前不重复子数组的左端点。

遍历数组，对于每个数字 $v$ ，如果 $d [v]$ 存在，那么我们更新 $j$ 为 $max (j, d [v])$ ，这样就保证了当前不重复子数组不包含 $v$ 。然后我们更新答案为 $max (ans, s [i] - s [j])$ ，最后更新 $d [v]$ 为 $i$ 。

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

func maximumUniqueSubarray(nums []int) (ans int) {
	d := [10001]int{}
	n := len(nums)
	s := make([]int, n+1)
	for i, v := range nums {
		s[i+1] = s[i] + v
	}
	for i, j := 1, 0; i <= n; i++ {
		v := nums[i-1]
		j = max(j, d[v])
		ans = max(ans, s[i]-s[j])
		d[v] = i
	}
	return
}

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

思考

方法一用前缀和与下标表。也可用滑动窗口维护当前互异段的和：右端纳入时若重复则左端弹出，省掉前缀数组。

题目实际上是让我们找出一个最长的子数组，该子数组中所有元素都不相同。我们可以用两个指针 $i$ 和 $j$ 分别指向子数组的左右边界，初始时 $i = 0$ , $j = 0$ 。另外，我们用一个哈希表 $vis$ 记录子数组中的元素。

遍历数组，对于每个数字 $x$ ，如果 $x$ 在 $vis$ 中，那么我们不断地将 $nums [i]$ 从 $vis$ 中移除，直到 $x$ 不在 $vis$ 中为止。这样我们就找到了一个不包含重复元素的子数组。我们将 $x$ 加入 $vis$ ，并更新子数组的和 $s$ ，然后更新答案 $ans = max (ans, s)$ 。

遍历结束后，我们就可以得到最大的子数组和。

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

func maximumUniqueSubarray(nums []int) (ans int) {
	vis := map[int]bool{}
	var s, i int
	for _, x := range nums {
		for vis[x] {
			s -= nums[i]
			vis[nums[i]] = false
			i++
		}
		vis[x] = true
		s += x
		ans = max(ans, s)
	}
	return
}

力扣原题 · Doocs 题解来源

1763. 最长的美好子字符串

简单2 种解法

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

题目、示例与约束

当一个字符串 s 包含的每一种字母的大写和小写形式同时出现在 s 中，就称这个字符串 s 是美好字符串。比方说，"abABB" 是美好字符串，因为 'A' 和 'a' 同时出现了，且 'B' 和 'b' 也同时出现了。然而，"abA" 不是美好字符串因为 'b' 出现了，而 'B' 没有出现。

给你一个字符串 s ，请你返回 s 最长的 美好子字符串 。如果有多个答案，请你返回最早出现的一个。如果不存在美好子字符串，请你返回一个空字符串。

示例 1：

输入：s = "YazaAay"
输出："aAa"
解释："aAa" 是一个美好字符串，因为这个子串中仅含一种字母，其小写形式 'a' 和大写形式 'A' 也同时出现了。
"aAa" 是最长的美好子字符串。

示例 2：

输入：s = "Bb"
输出："Bb"
解释："Bb" 是美好字符串，因为 'B' 和 'b' 都出现了。整个字符串也是原字符串的子字符串。

示例 3：

输入：s = "c"
输出：""
解释：没有美好子字符串。

示例 4：

输入：s = "dDzeE"
输出："dD"
解释："dD" 和 "eE" 都是最长美好子字符串。
由于有多个美好子字符串，返回 "dD" ，因为它出现得最早。

提示：

1 <= s.length <= 100
s 只包含大写和小写英文字母。

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

思考

美好子串要求每个出现的字母大小写都在。 $n$ 很小，可枚举全部子串。

固定左端 $i$ ，向右扩张并用集合记录字符；集合内每个字母的大小写都在且更长时更新答案。同长时保留先出现的那段。

我们可以直接枚举所有子串的起点位置 $i$ ，找到以该位置所在的字符为首字符的所有子串，用哈希表 $s$ 记录子串的所有字符。

如果子串中存在一个字母找不到对应的大写字母或者小写字母，那么不满足条件，否则取最长的且最早出现的子串。

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

func longestNiceSubstring(s string) string {
	n := len(s)
	k, mx := -1, 0
	for i := 0; i < n; i++ {
		ss := map[byte]bool{}
		for j := i; j < n; j++ {
			ss[s[j]] = true
			ok := true
			for a := range ss {
				b := a ^ 32
				if !(ss[a] && ss[b]) {
					ok = false
					break
				}
			}
			if ok && mx < j-i+1 {
				mx = j - i + 1
				k = i
			}
		}
	}
	if k < 0 {
		return ""
	}
	return s[k : k+mx]
}

方法二：枚举 + 位运算 · Go 实现

思考

方法一对每个窗口扫描集合判断大小写，多一个 $C$ 因子。字母只有 $26$ 对，可用两个位掩码分别记小写与大写，窗口合法当且仅当两掩码相等。

与方法一类似，我们可以直接枚举所有子串的起点位置 $i$ ，找到以该位置所在的字符为首字符的所有子串，用两个整数 $l o w e r$ 和 $u p p e r$ 分别记录子串中小写字母和大写字母的出现情况。

判断子串是否满足条件，只需要判断 $l o w e r$ 和 $u p p e r$ 中对应的位是否都为 $1$ 即可。

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

func longestNiceSubstring(s string) string {
	n := len(s)
	k, mx := -1, 0
	for i := 0; i < n; i++ {
		var lower, upper int
		for j := i; j < n; j++ {
			if unicode.IsLower(rune(s[j])) {
				lower |= 1 << (s[j] - 'a')
			} else {
				upper |= 1 << (s[j] - 'A')
			}
			if lower == upper && mx < j-i+1 {
				mx = j - i + 1
				k = i
			}
		}
	}
	if k < 0 {
		return ""
	}
	return s[k : k+mx]
}

力扣原题 · Doocs 题解来源

1839. 所有元音按顺序排布的最长子字符串

中等1 种解法

标签：字符串、滑动窗口

题目、示例与约束

当一个字符串满足如下条件时，我们称它是 美丽的 ：

所有 5 个英文元音字母（'a' ，'e' ，'i' ，'o' ，'u'）都必须至少出现一次。
这些元音字母的顺序都必须按照 字典序 升序排布（也就是说所有的 'a' 都在 'e' 前面，所有的 'e' 都在 'i' 前面，以此类推）

比方说，字符串 "aeiou" 和 "aaaaaaeiiiioou" 都是 美丽的 ，但是 "uaeio" ，"aeoiu" 和 "aaaeeeooo" 不是美丽的 。

给你一个只包含英文元音字母的字符串 word ，请你返回 word 中 最长美丽子字符串的长度 。如果不存在这样的子字符串，请返回 0 。

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

示例 1：

输入：word = "aeiaaioaaaaeiiiiouuuooaauuaeiu"
输出：13
解释：最长子字符串是 "aaaaeiiiiouuu" ，长度为 13 。

示例 2：

输入：word = "aeeeiiiioooauuuaeiou"
输出：5
解释：最长子字符串是 "aeiou" ，长度为 5 。

示例 3：

输入：word = "a"
输出：0
解释：没有美丽子字符串，所以返回 0 。

提示：

1 <= word.length <= 5 * 10⁵
word 只包含字符 'a'，'e'，'i'，'o' 和 'u' 。

方法一：双指针 + 模拟 · Go 实现

思考

美丽子串必须按 $a, e, i, o, u$ 的顺序各至少出现一次，且中间不能回退。暴力枚举左右端再检查， $n \leq 10^{5}$ 不可行。

先把相同字母的连续段压成 $(字母, 长度)$ 。美丽串恰好对应连续五段且字母拼成 $aeiou$ ，其长度之和即为候选。线性扫描这些段即可。

我们可以先将字符串 word 做个转化，比如对于 word="aaaeiouu"，我们可以将其转化为数据项 ('a', 3), ('e', 1), ('i', 1), ('o', 1), ('u', 2)，存放在数组 arr 中。其中每个数据项的第一个元素表示元音字母，第二个元素表示该元音字母连续出现的次数。这部分转化可以通过双指针来实现。

接下来，我们遍历数组 arr，每次取相邻的 $5$ 个数据项，判断这些数据项中的元音字母是否分别为 'a', 'e', 'i', 'o', 'u'，如果是，则计算这 $5$ 个数据项中元音字母的总次数，即为当前的美丽子字符串的长度，更新答案的最大值即可。

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

func longestBeautifulSubstring(word string) (ans int) {
	arr := []pair{}
	n := len(word)
	for i := 0; i < n; {
		j := i
		for j < n && word[j] == word[i] {
			j++
		}
		arr = append(arr, pair{word[i], j - i})
		i = j
	}
	for i := 0; i < len(arr)-4; i++ {
		a, b, c, d, e := arr[i], arr[i+1], arr[i+2], arr[i+3], arr[i+4]
		if a.c == 'a' && b.c == 'e' && c.c == 'i' && d.c == 'o' && e.c == 'u' {
			ans = max(ans, a.v+b.v+c.v+d.v+e.v)
		}
	}
	return
}

type pair struct {
	c byte
	v int
}

力扣原题 · Doocs 题解来源

1852. 每个子数组的数字种类数 🔒

中等2 种解法

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

题目、示例与约束

给你一个长度为 n 的整数数组 nums 与一个整数 k。你的任务是找到 nums 所有长度为 k 的子数组中不同元素的数量。

返回一个数组 ans，其中 ans[i] 是对于每个索引 0 <= i < n - k，nums[i..(i + k - 1)] 中不同元素的数量。

示例 1:

输入: nums = [1,2,3,2,2,1,3], k = 3
输出: [3,2,2,2,3]
解释：每个子数组的数字种类计算方法如下：
- nums[0..2] = [1,2,3] 所以 ans[0] = 3
- nums[1..3] = [2,3,2] 所以 ans[1] = 2
- nums[2..4] = [3,2,2] 所以 ans[2] = 2
- nums[3..5] = [2,2,1] 所以 ans[3] = 2
- nums[4..6] = [2,1,3] 所以 ans[4] = 3

示例 2:

输入: nums = [1,1,1,1,2,3,4], k = 4
输出: [1,2,3,4]
解释: 每个子数组的数字种类计算方法如下：
- nums[0..3] = [1,1,1,1] 所以 ans[0] = 1
- nums[1..4] = [1,1,1,2] 所以 ans[1] = 2
- nums[2..5] = [1,1,2,3] 所以 ans[2] = 3
- nums[3..6] = [1,2,3,4] 所以 ans[3] = 4

提示:

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

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

思考

对每个长为 $k$ 的窗口统计不同数字个数。 $n \leq 10^{5}$ ，每个窗口单独用集合去重会超时。

维护窗口内的频次表：右端进入加一，左端离开减一至 $0$ 则删除。表的大小即当前窗口的不同个数，窗口滑动一遍即可。

我们用一个哈希表 $c n t$ 记录每个长度为 $k$ 的子数组中数字的出现次数。

接下来，我们首先遍历数组前 $k$ 个元素，记录每个元素出现的次数，遍历后，我们将哈希表的大小作为答案数组的第一个元素。

然后，我们从下标 $k$ 继续遍历数组，每次遍历时，我们将当前元素的出现次数加一，并且将当前元素左边的元素的出现次数减一，如果减一后的出现次数为 $0$ ，则将其从哈希表中删除，然后将哈希表的大小作为答案数组的下一个元素，继续遍历。

遍历结束后，我们返回答案数组。

时间复杂度 $O (n)$ ，空间复杂度 $O (k)$ 。其中 $n$ 为数组 $n u m s$ 的长度，而 $k$ 为题目给定的参数。

func distinctNumbers(nums []int, k int) []int {
	cnt := map[int]int{}
	for _, x := range nums[:k] {
		cnt[x]++
	}
	ans := []int{len(cnt)}
	for i := k; i < len(nums); i++ {
		cnt[nums[i]]++
		cnt[nums[i-k]]--
		if cnt[nums[i-k]] == 0 {
			delete(cnt, nums[i-k])
		}
		ans = append(ans, len(cnt))
	}
	return ans
}

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

思考

方法一用哈希表，常数与哈希开销较大。数值范围不超过 $10^{5}$ ，可用数组代替映射。窗口逻辑不变，只是把计数下标换成数值本身。

我们也可以用数组来代替哈希表，这样可以提升一定的性能。

时间复杂度 $O (n)$ ，空间复杂度 $O (M)$ 。其中 $n$ 为数组 $n u m s$ 的长度，而 $M$ 为数组 $n u m s$ 中的最大值，本题中 $M \leq 10^{5}$ 。

func distinctNumbers(nums []int, k int) (ans []int) {
	m := slices.Max(nums)
	cnt := make([]int, m+1)
	v := 0
	for _, x := range nums[:k] {
		cnt[x]++
		if cnt[x] == 1 {
			v++
		}
	}
	ans = append(ans, v)
	for i := k; i < len(nums); i++ {
		cnt[nums[i]]++
		if cnt[nums[i]] == 1 {
			v++
		}
		cnt[nums[i-k]]--
		if cnt[nums[i-k]] == 0 {
			v--
		}
		ans = append(ans, v)
	}
	return
}

力扣原题 · Doocs 题解来源

1876. 长度为三且各字符不同的子字符串

简单1 种解法

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

题目、示例与约束

如果一个字符串不含有任何重复字符，我们称这个字符串为好字符串。

给你一个字符串 s ，请你返回 s 中长度为 3 的 好子字符串 的数量。

注意，如果相同的好子字符串出现多次，每一次都应该被记入答案之中。

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

示例 1：

输入：s = "xyzzaz"
输出：1
解释：总共有 4 个长度为 3 的子字符串："xyz"，"yzz"，"zza" 和 "zaz" 。
唯一的长度为 3 的好子字符串是 "xyz" 。

示例 2：

输入：s = "aababcabc"
输出：4
解释：总共有 7 个长度为 3 的子字符串："aab"，"aba"，"bab"，"abc"，"bca"，"cab" 和 "abc" 。
好子字符串包括 "abc"，"bca"，"cab" 和 "abc" 。

提示：

1 <= s.length <= 100
s 只包含小写英文字母。

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

思考

统计长为 $3$ 且字符互不相同的子串。窗口很短，枚举每个起点检查三位即可；写成可扩展的滑动窗口则能推广到任意 $k$ 。

维护无重复字符的窗口： $m a s k$ 标记窗口内字母，右端遇重复则收缩左端。窗口长度至少为 $3$ 时，以右端结尾的长为 $3$ 的子串一定互异，计入答案。

我们可以维护一个滑动窗口，使得窗口内的字符不重复。初始时，我们用一个长度为 $26$ 的二进制整数 $mask$ 表示窗口内的字符，其中第 $i$ 位为 $1$ 表示字符 $i$ 在窗口内出现过，否则表示字符 $i$ 在窗口内没有出现过。

然后，我们遍历字符串 $s$ ，对于每一个位置 $r$ ，如果 $s [r]$ 在窗口内出现过，我们需要将窗口的左边界 $l$ 右移，直到窗口内不再有重复的字符。在这之后，我们将 $s [r]$ 加入窗口内，此时如果窗口的长度大于等于 $3$ ，那么我们就找到了一个以 $s [r]$ 结尾的长度为 $3$ 的好子字符串。

遍历结束后，我们就找到了所有的好子字符串的数量。

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

该解法可以拓展到长度为 $k$ 的好子字符串的数量。

func countGoodSubstrings(s string) (ans int) {
	mask, l := 0, 0
	for r, c := range s {
		x := int(c - 'a')
		for (mask>>x)&1 == 1 {
			y := int(s[l] - 'a')
			l++
			mask ^= 1 << y
		}
		mask |= 1 << x
		if r-l+1 >= 3 {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1984. 学生分数的最小差值

简单1 种解法

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

题目、示例与约束

给你一个 下标从 0 开始 的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。

从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的差值达到 最小化 。

返回可能的 最小差值 。

示例 1：

输入：nums = [90], k = 1
输出：0
解释：选出 1 名学生的分数，仅有 1 种方法：
- [90] 最高分和最低分之间的差值是 90 - 90 = 0
可能的最小差值是 0

示例 2：

输入：nums = [9,4,1,7], k = 2
输出：2
解释：选出 2 名学生的分数，有 6 种方法：
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 4 = 5
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 1 = 8
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 7 = 2
- [9,4,1,7] 最高分和最低分之间的差值是 4 - 1 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 4 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 1 = 6
可能的最小差值是 2

提示：

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

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

思考

选 $k$ 个分数使最大最小之差最小。排序后最优的 $k$ 个必连续，否则两端只会更远。

对每个窗口 $nums [i + k - 1] - nums [i]$ 取最小。

我们可以将学生的分数按照升序排序，然后使用滑动窗口的方法，每次取大小为 $k$ 的窗口，计算窗口内的最大值和最小值的差值，最后取所有窗口的差值的最小值。

为什么是取连续的 $k$ 个学生的分数呢？因为如果不连续，那么最大值和最小值的的差值可能不变，或者变大，但一定不会变小。因此，我们只需要考虑排序后的连续的 $k$ 个学生的分数。

时间复杂度 $O (n \times \log n)$ ，空间复杂度 $O (\log n)$ 。其中 $n$ 是学生的数量。

func minimumDifference(nums []int, k int) int {
	sort.Ints(nums)
	ans := 100000
	for i := 0; i < len(nums)-k+1; i++ {
		ans = min(ans, nums[i+k-1]-nums[i])
	}
	return ans
}

力扣原题 · Doocs 题解来源

2067. 等计数子串的数量 🔒

中等1 种解法

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

题目、示例与约束

给你一个下标从 0 开始的字符串 s，只包含小写英文字母和一个整数 count。如果 s 的子串中的每种字母在子串中恰好出现 count 次，这个子串就被称为 等计数子串。

返回 s 中 等计数子串 的个数。

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

示例 1:

输入: s = "aaabcbbcc", count = 3
输出: 3
解释:
从下标 0 开始到下标 2 结束的子串是 "aaa"。
字母 “a” 在子串中恰好出现了 3 次。
从下标 3 开始到下标 8 结束的子串是 "bcbbcc"。
字母 “b” 和 “c” 在子串中恰好出现了 3 次。
从下标 0 开始到下标 8 结束的子串是 "aaabcbbcc"。
字母 “a”、“b” 和 “c” 在子串中恰好出现了 3 次。

示例 2:

输入: s = "abcd", count = 2
输出: 0
解释:
每种字母在 s 中出现的次数小于 count。
因此，s 中没有子串是等计数子串，返回 0。

示例 3:

输入: s = "a", count = 5
输出: 0
解释:
每种字母在 s 中出现的次数小于 count。
因此，s 中没有子串是等计数子串，返回 0。

提示:

1 <= s.length <= 3 * 10⁴
1 <= count <= 3 * 10⁴
s 只由小写英文字母组成。

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

思考

子串中出现的每种字母都恰有 $c o u n t$ 次。字母种类 $i \in [1, 26]$ 时，窗口长度锁定为 $i \cdot c o u n t$ ，可滑动统计。

维护窗口内「频次恰为 $c o u n t$ 」的字母数 $t$ ，进出窗口时调整。 $i = t$ 则该窗口合法。

我们可以在 $[1. .26]$ 范围内枚举子串的字母种类数 $i$ ，那么子串长度就是 $i \times c o u n t$ 。

接下来，我们将当前子串长度作为窗口的大小，统计窗口大小中有多少种字母的个数为 $c o u n t$ ，记录在 $t$ 中。如果此时 $i = t$ ，说明当前窗口中的字母个数都为 $c o u n t$ ，那么就可以将答案加一。

时间复杂度 $O (n \times C)$ ，空间复杂度 $O (C)$ 。其中 $n$ 为字符串 $s$ 的长度，而 $C$ 为字母的种类数，本题中 $C = 26$ 。

func equalCountSubstrings(s string, count int) (ans int) {
	n := len(s)
	for i := 1; i < 27 && i*count <= n; i++ {
		k := i * count
		cnt := [26]int{}
		t := 0
		for j, c := range s {
			a := c - 'a'
			cnt[a]++
			if cnt[a] == count {
				t++
			} else if cnt[a] == count+1 {
				t--
			}
			if j >= k {
				b := s[j-k] - 'a'
				cnt[b]--
				if cnt[b] == count {
					t++
				} else if cnt[b] == count-1 {
					t--
				}
			}
			if i == t {
				ans++
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2090. 半径为 k 的子数组平均值

中等1 种解法

标签：数组、滑动窗口

题目、示例与约束

给你一个下标从 0 开始的数组 nums ，数组中有 n 个整数，另给你一个整数 k 。

半径为 k 的子数组平均值 是指：nums 中一个以下标 i 为中心且半径为 k 的子数组中所有元素的平均值，即下标在 i - k 和 i + k 范围（含 i - k 和 i + k）内所有元素的平均值。如果在下标 i 前或后不足 k 个元素，那么 半径为 k 的子数组平均值 是 -1 。

构建并返回一个长度为 n 的数组 avgs ，其中 avgs[i] 是以下标 i 为中心的子数组的 半径为 k 的子数组平均值 。

x 个元素的 平均值 是 x 个元素相加之和除以 x ，此时使用截断式 整数除法 ，即需要去掉结果的小数部分。

例如，四个元素 2、3、1 和 5 的平均值是 (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75，截断后得到 2 。

示例 1：

输入：nums = [7,4,3,9,1,8,5,2,6], k = 3
输出：[-1,-1,-1,5,4,4,-1,-1,-1]
解释：
- avg[0]、avg[1] 和 avg[2] 是 -1 ，因为在这几个下标前的元素数量都不足 k 个。
- 中心为下标 3 且半径为 3 的子数组的元素总和是：7 + 4 + 3 + 9 + 1 + 8 + 5 = 37 。
  使用截断式 整数除法，avg[3] = 37 / 7 = 5 。
- 中心为下标 4 的子数组，avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4 。
- 中心为下标 5 的子数组，avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4 。
- avg[6]、avg[7] 和 avg[8] 是 -1 ，因为在这几个下标后的元素数量都不足 k 个。

示例 2：

输入：nums = [100000], k = 0
输出：[100000]
解释：
- 中心为下标 0 且半径 0 的子数组的元素总和是：100000 。
  avg[0] = 100000 / 1 = 100000 。

示例 3：

输入：nums = [8], k = 100000
输出：[-1]
解释：
- avg[0] 是 -1 ，因为在下标 0 前后的元素数量均不足 k 。

提示：

n == nums.length
1 <= n <= 10⁵
0 <= nums[i], k <= 10⁵

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

思考

窗口长度固定为 $2 k + 1$ ，两端不足则答案为 $- 1$ 。 $n \leq 10^{5}$ ，滑动维护窗口和。

右端进入、左端离开，中心下标为 $i - k$ ，整除得到平均值。

半径为 $k$ 的子数组的长度为 $k \times 2 + 1$ ，因此我们可以维护一个大小为 $k \times 2 + 1$ 的窗口，记窗口中的所有元素和为 $s$ 。

我们创建一个长度为 $n$ 的答案数组 $ans$ ，初始时每个元素都为 $- 1$ 。

接下来，我们遍历数组 $nums$ ，将 $nums [i]$ 的值加到窗口的和 $s$ 中，如果此时 $i \geq k \times 2$ ，说明此时窗口大小为 $k \times 2 + 1$ ，那么 $ans [i - k] = \frac{s}{k \times 2 + 1}$ ，然后我们将 $nums [i - k \times 2]$ 的值从窗口和 $s$ 中移出。继续遍历下个元素。

最后返回答案数组即可。

时间复杂度 $O (n)$ ，其中 $n$ 为数组 $nums$ 的长度。忽略答案数组的空间消耗，空间复杂度 $O (1)$ 。

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

力扣原题 · Doocs 题解来源

2107. 分享 K 个糖果后独特口味的数量 🔒

中等1 种解法

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

题目、示例与约束

您将获得一个 从0开始的 整数数组 candies ，其中 candies[i] 表示第 i 个糖果的味道。你妈妈想让你和你妹妹分享这些糖果，给她 k 个连续的糖果，但你想保留尽可能多的糖果口味。
在与妹妹分享后，返回最多可保留的独特口味的糖果。

示例 1：

输入: candies = [1,2,2,3,4,3], k = 3
输出: 3
解释:
将[1,3]（含[2,2,3]）范围内的糖果加入[2,2,3]口味。
你可以吃各种口味的糖果[1,4,3]。
有3种独特的口味，所以返回3。

示例 2:

输入: candies = [2,2,2,2,3,3], k = 2
输出: 2
解释:
在[3,4]范围内（含[2,3]）的糖果中加入[2,3]口味。
你可以吃各种口味的糖果[2,2,2,3]。
有两种独特的口味，所以返回2。
请注意，你也可以分享口味为[2,2]的糖果，吃口味为[2,2,3,3]的糖果。

示例 3:

输入: candies = [2,4,5], k = 0
输出: 3
解释:
你不必给任何糖果。
你可以吃各种口味的糖果[2,4,5]。
有3种独特的口味，所以返回3。

提示:

0 <= candies.length <= 10⁵
1 <= candies[i] <= 10⁵
0 <= k <= candies.length

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

思考

分出的 $k$ 颗糖必须是连续一段，自己留下的是这段的补集。若对每个窗口重建口味集合，每次 $O (n)$ ，总时间 $O (n^{2})$ ，在 $n \leq 10^{5}$ 时不可行。

窗口长度固定为 $k$ ，右移一格时只有两端各一颗糖进出补集。用计数表维护窗口外每种口味的个数，种类数即表的大小。

初始将 $candies [k :]$ 放入计数表，再滑过每个长度为 $k$ 的窗口，更新两端并记录种类数的最大值。

我们可以维护一个大小为 $k$ 的滑动窗口，窗口外的糖果为自己的，窗口内的 $k$ 个糖果分给妹妹和妈妈。我们可以用哈希表 $c n t$ 记录窗口外的糖果口味以及对应的数量。

初始时，哈希表 $c n t$ 中存储的是 $c a n d i e s [k]$ 到 $c a n d i e s [n - 1]$ 的糖果口味以及对应的数量。此时糖果口味的种类数为哈希表 $c n t$ 的大小，即 $a n s = c n t . s i z e ()$ 。

接下来，我们遍历 $[k, . . n - 1]$ 范围内的糖果，将当前糖果 $c a n d i e s [i]$ 加入窗口内，同时将窗口左侧的糖果 $c a n d i e s [i - k]$ 移出窗口外。然后我们更新哈希表 $c n t$ ，并且更新糖果口味的种类数 $a n s$ 为 $m a x (a n s, c n t . s i z e ())$ 。

遍历完所有糖果后，我们即可得到最多可保留的独特口味的糖果。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为糖果的数量。

func shareCandies(candies []int, k int) (ans int) {
	cnt := map[int]int{}
	for _, c := range candies[k:] {
		cnt[c]++
	}
	ans = len(cnt)
	for i := k; i < len(candies); i++ {
		cnt[candies[i-k]]++
		cnt[candies[i]]--
		if cnt[candies[i]] == 0 {
			delete(cnt, candies[i])
		}
		ans = max(ans, len(cnt))
	}
	return
}

力扣原题 · Doocs 题解来源

2134. 最少交换次数来组合所有的 1 II

中等1 种解法

标签：数组、滑动窗口

题目、示例与约束

交换定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。

环形数组是一个数组，可以认为 第一个 元素和 最后一个 元素相邻。

给你一个 二进制环形 数组 nums ，返回在 任意位置 将数组中的所有 1 聚集在一起需要的最少交换次数。

示例 1：

输入：nums = [0,1,0,1,1,0,0]
输出：1
解释：这里列出一些能够将所有 1 聚集在一起的方案：
[0,0,1,1,1,0,0] 交换 1 次。
[0,1,1,1,0,0,0] 交换 1 次。
[1,1,0,0,0,0,1] 交换 2 次（利用数组的环形特性）。
无法在交换 0 次的情况下将数组中的所有 1 聚集在一起。
因此，需要的最少交换次数为 1 。

示例 2：

输入：nums = [0,1,1,1,0,0,1,1,0]
输出：2
解释：这里列出一些能够将所有 1 聚集在一起的方案：
[1,1,1,0,0,0,0,1,1] 交换 2 次（利用数组的环形特性）。
[1,1,1,1,1,0,0,0,0] 交换 2 次。
无法在交换 0 次或 1 次的情况下将数组中的所有 1 聚集在一起。
因此，需要的最少交换次数为 2 。

示例 3：

输入：nums = [1,1,0,0,1]
输出：0
解释：得益于数组的环形特性，所有的 1 已经聚集在一起。
因此，需要的最少交换次数为 0 。

提示：

1 <= nums.length <= 10⁵
nums[i] 为 0 或者 1

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

思考

环形数组中把全部 $1$ 换到一起，等价于找一个长度为 $k = count (1)$ 的窗口，使其中 $1$ 最多，答案为 $k$ 减该最大值。枚举所有窗口若每次重算计数则为二次。

窗口长度固定，环形只要把下标对 $n$ 取模继续滑 $k$ 步。先统计前 $k$ 个 $1$ 的个数，再每次加右端、减左端。

扫完一圈后返回 $k - mx$ 。

我们先统计数组中 $1$ 的个数，记为 $k$ ，那么题目实际上就是求一个长度为 $k$ 的环形子数组，使得子数组中 $1$ 的个数最多，那么最少交换次数就是 $k$ 减去子数组中 $1$ 的个数最多的那个子数组中 $1$ 的个数。

我们可以使用滑动窗口来解决这个问题，首先统计数组中前 $k$ 个元素中 $1$ 的个数，记为 $c n t$ ，然后我们维护一个长度为 $k$ 的滑动窗口，每次向右移动一个位置，更新 $c n t$ ，同时更新最大的 $c n t$ 值，即 $m x = max (m x, c n t)$ ，最后答案就是 $k - m x$ 。

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

func minSwaps(nums []int) int {
	k := 0
	for _, x := range nums {
		k += x
	}
	cnt := 0
	for i := 0; i < k; i++ {
		cnt += nums[i]
	}
	mx := cnt
	n := len(nums)
	for i := k; i < n+k; i++ {
		cnt += nums[i%n] - nums[(i-k+n)%n]
		mx = max(mx, cnt)
	}
	return k - mx
}

力扣原题 · Doocs 题解来源

2156. 查找给定哈希值的子串

困难1 种解法

标签：字符串、滑动窗口、哈希函数、滚动哈希

题目、示例与约束

给定整数 p 和 m ，一个长度为 k 且下标从 0 开始的字符串 s 的哈希值按照如下函数计算：

hash(s, p, m) = (val(s[0]) * p⁰ + val(s[1]) * p¹ + ... + val(s[k-1]) * p^k-1) mod m.

其中 val(s[i]) 表示 s[i] 在字母表中的下标，从 val('a') = 1 到 val('z') = 26 。

给你一个字符串 s 和整数 power，modulo，k 和 hashValue 。请你返回 s 中 第一个 长度为 k 的子串 sub ，满足 hash(sub, power, modulo) == hashValue 。

测试数据保证一定存在至少一个这样的子串。

子串定义为一个字符串中连续非空字符组成的序列。

示例 1：

输入：s = "leetcode", power = 7, modulo = 20, k = 2, hashValue = 0
输出："ee"
解释："ee" 的哈希值为 hash("ee", 7, 20) = (5 * 1 + 5 * 7) mod 20 = 40 mod 20 = 0 。
"ee" 是长度为 2 的第一个哈希值为 0 的子串，所以我们返回 "ee" 。

示例 2：

输入：s = "fbxzaad", power = 31, modulo = 100, k = 3, hashValue = 32
输出："fbx"
解释："fbx" 的哈希值为 hash("fbx", 31, 100) = (6 * 1 + 2 * 31 + 24 * 31²) mod 100 = 23132 mod 100 = 32 。
"bxz" 的哈希值为 hash("bxz", 31, 100) = (2 * 1 + 24 * 31 + 26 * 31²) mod 100 = 25732 mod 100 = 32 。
"fbx" 是长度为 3 的第一个哈希值为 32 的子串，所以我们返回 "fbx" 。
注意，"bxz" 的哈希值也为 32 ，但是它在字符串中比 "fbx" 更晚出现。

提示：

1 <= k <= s.length <= 2 * 10⁴
1 <= power, modulo <= 10⁹
0 <= hashValue < modulo
s 只包含小写英文字母。
测试数据保证一定存在满足条件的子串。

方法一：滑动窗口 + 倒序遍历 · Go 实现

思考

需要长度为 $k$ 、哈希等于给定值的最靠后子串。正着滑窗时去掉左端相当于除以 $p$ 再取模，模逆元处理麻烦。 $n \leq 10^{5}$ ，需线性滑窗。

倒序计算 Rabin–Karp：窗口右移（在原串上左移）时，去掉旧的最高位、乘 $p$ 再加新的最低位，只需乘法和取模。

先算末尾 $k$ 个字符的哈希并记下 $p^{k - 1}$ ，再向左滑，每次命中则更新起点。

我们可以维护一个长度为 $k$ 的滑动窗口，用来计算子串的哈希值。考虑到如果正序遍历字符串，在哈希值的计算中，涉及到除法取模的操作，处理起来比较麻烦。因此我们可以倒序遍历字符串，这样在计算哈希值的时候，只需要乘法和取模操作。

我们首先计算字符串末尾的 $k$ 个字符的哈希值，然后从字符串末尾开始倒序遍历，每次计算当前窗口的哈希值，如果等于给定的哈希值，我们就找到了一个满足条件的子串，更新答案字符串的起始位置。

最后返回答案字符串即可。

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

func subStrHash(s string, power int, modulo int, k int, hashValue int) string {
	h, p := 0, 1
	n := len(s)
	for i := n - 1; i >= n-k; i-- {
		val := int(s[i] - 'a' + 1)
		h = (h*power%modulo + val) % modulo
		if i != n-k {
			p = p * power % modulo
		}
	}
	j := n - k
	for i := n - k - 1; i >= 0; i-- {
		pre := int(s[i+k] - 'a' + 1)
		cur := int(s[i] - 'a' + 1)
		h = ((h-pre*p%modulo+modulo)*power%modulo + cur) % modulo
		if h == hashValue {
			j = i
		}
	}
	return s[j : j+k]
}

力扣原题 · Doocs 题解来源

2260. 必须拿起的最小连续卡牌数

中等1 种解法

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

题目、示例与约束

给你一个整数数组 cards ，其中 cards[i] 表示第 i 张卡牌的值。如果两张卡牌的值相同，则认为这一对卡牌匹配。

返回你必须拿起的最小连续卡牌数，以使在拿起的卡牌中有一对匹配的卡牌。如果无法得到一对匹配的卡牌，返回 -1 。

示例 1：

输入：cards = [3,4,2,3,4,7]
输出：4
解释：拿起卡牌 [3,4,2,3] 将会包含一对值为 3 的匹配卡牌。注意，拿起 [4,2,3,4] 也是最优方案。

示例 2：

输入：cards = [1,0,5,3]
输出：-1
解释：无法找出含一对匹配卡牌的一组连续卡牌。

提示：

1 <= cards.length <= 10⁵
0 <= cards[i] <= 10⁶

方法一：哈希表 · Go 实现

思考

要拿起至少两张相同点数的连续段，长度尽量短。 $n \leq 10^{5}$ ，枚举左右端再检查是否有重复过慢。最短段一定以某次「同一点数的相邻两次出现」为两端。

哈希表记下每个点数上次出现的下标，再次遇到时用 $i - last [x] + 1$ 更新最短长度。没有重复则返回 $- 1$ 。

我们初始化答案为 $+ \infty$ ，遍历数组，对于每个数字 $x$ ，如果 $last [x]$ 存在，则表示 $x$ 有一对匹配卡牌，此时更新答案为 $ans = min (ans, i - last [x] + 1)$ ，最后如果答案为 $+ \infty$ ，则返回 $- 1$ ，否则返回答案。

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

func minimumCardPickup(cards []int) int {
	last := map[int]int{}
	n := len(cards)
	ans := n + 1
	for i, x := range cards {
		if j, ok := last[x]; ok && ans > i-j+1 {
			ans = i - j + 1
		}
		last[x] = i
	}
	if ans > n {
		return -1
	}
	return ans
}

力扣原题 · Doocs 题解来源

2269. 找到一个数字的 K 美丽值

简单2 种解法

标签：数学、字符串、滑动窗口

题目、示例与约束

一个整数 num 的 k 美丽值定义为 num 中符合以下条件的 子字符串 数目：

子字符串长度为 k 。
子字符串能整除 num 。

给你整数 num 和 k ，请你返回 num 的 k 美丽值。

注意：

允许有前缀 0 。
0 不能整除任何值。

一个 子字符串 是一个字符串里的连续一段字符序列。

示例 1：

输入：num = 240, k = 2
输出：2
解释：以下是 num 里长度为 k 的子字符串：
- "240" 中的 "24" ：24 能整除 240 。
- "240" 中的 "40" ：40 能整除 240 。
所以，k 美丽值为 2 。

示例 2：

输入：num = 430043, k = 2
输出：2
解释：以下是 num 里长度为 k 的子字符串：
- "430043" 中的 "43" ：43 能整除 430043 。
- "430043" 中的 "30" ：30 不能整除 430043 。
- "430043" 中的 "00" ：0 不能整除 430043 。
- "430043" 中的 "04" ：4 不能整除 430043 。
- "430043" 中的 "43" ：43 能整除 430043 。
所以，k 美丽值为 2 。

提示：

1 <= num <= 10⁹
1 <= k <= num.length （将 num 视为字符串）

方法一：枚举 · Go 实现

思考

$k$ 美是长度为 $k$ 且能整除原数的子串个数。 $n u m \leq 10^{9}$ ，十进制位数很少，枚举每个长为 $k$ 的子串转成整数即可，注意除数不能为 $0$ 。

把 $n u m$ 转成字符串，对每个起点 $i$ 取 $s [i : i + k]$ 。

我们可以将 $n u m$ 转换为字符串 $s$ ，然后枚举 $s$ 的所有长度为 $k$ 的子字符串，将其转换为整数 $t$ ，判断 $t$ 是否能整除 $n u m$ ，如果能则答案加一。

时间复杂度 $O (\log n u m \times k)$ ，空间复杂度 $O (\log n u m + k)$ 。

func divisorSubstrings(num int, k int) int {
	ans := 0
	s := strconv.Itoa(num)
	for i := 0; i < len(s)-k+1; i++ {
		t, _ := strconv.Atoi(s[i : i+k])
		if t > 0 && num%t == 0 {
			ans++
		}
	}
	return ans
}

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

思考

方法一每次切片再转整数，有字符串开销。窗口在十进制上滑动时，去掉最低位、在最高位加上新数字，即可 $O (1)$ 更新窗口值。

先从低位取出 $k$ 位得到 $x$ ，再反复 $x \leftarrow x / / 10$ 并在高位补上新数位，同时判断整除。额外空间 $O (1)$ 。

我们可以维护一个长度为 $k$ 的滑动窗口，初始时窗口中包含 $n u m$ 的最低 $k$ 位数字，然后每次向右移动一位，更新窗口中的数字，判断窗口中的数字是否能整除 $n u m$ ，如果能则答案加一。

时间复杂度 $O (\log n u m)$ ，空间复杂度 $O (1)$ 。

func divisorSubstrings(num int, k int) (ans int) {
	x, p, t := 0, 1, num
	for ; k > 0; k-- {
		v := t % 10
		t /= 10
		x = p*v + x
		p *= 10
	}
	if x != 0 && num%x == 0 {
		ans++
	}
	for p /= 10; t > 0; t /= 10 {
		x /= 10
		v := t % 10
		x = p*v + x
		if x != 0 && num%x == 0 {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2379. 得到 K 个黑块的最少涂色次数

简单1 种解法

标签：字符串、滑动窗口

题目、示例与约束

给你一个长度为 n 下标从 0 开始的字符串 blocks ，blocks[i] 要么是 'W' 要么是 'B' ，表示第 i 块的颜色。字符 'W' 和 'B' 分别表示白色和黑色。

给你一个整数 k ，表示想要连续黑色块的数目。

每一次操作中，你可以选择一个白色块将它涂成黑色块。

请你返回至少出现一次连续 k 个黑色块的最少操作次数。

示例 1：

输入：blocks = "WBBWWBBWBW", k = 7
输出：3
解释：
一种得到 7 个连续黑色块的方法是把第 0 ，3 和 4 个块涂成黑色。
得到 blocks = "BBBBBBBWBW" 。
可以证明无法用少于 3 次操作得到 7 个连续的黑块。
所以我们返回 3 。

示例 2：

输入：blocks = "WBWBBBW", k = 2
输出：0
解释：
不需要任何操作，因为已经有 2 个连续的黑块。
所以我们返回 0 。

提示：

n == blocks.length
1 <= n <= 100
blocks[i] 要么是 'W' ，要么是 'B' 。
1 <= k <= n

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

思考

把某一段长 $k$ 的窗口染成全黑，代价等于其中白块个数。扫描所有窗口即可，不必搜索染色方案。

先统计前 $k$ 个白块，再滑窗加减两端，维护白块数的最小值。

我们观察发现，题目实际上求的是一个 $k$ 大小的滑动窗口中白色块的最小数量。

因此，我们只需要遍历字符串 $b l o c k s$ ，用一个变量 $c n t$ 统计当前窗口中白色块的数量，然后用一个变量 $a n s$ 维护最小值即可。

遍历结束后即可得到答案。

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

func minimumRecolors(blocks string, k int) int {
	cnt := strings.Count(blocks[:k], "W")
	ans := cnt
	for i := k; i < len(blocks); i++ {
		if blocks[i] == 'W' {
			cnt++
		}
		if blocks[i-k] == 'W' {
			cnt--
		}
		if ans > cnt {
			ans = cnt
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2401. 最长优雅子数组

中等1 种解法

标签：位运算、数组、滑动窗口

题目、示例与约束

给你一个由正整数组成的数组 nums 。

如果 nums 的子数组中位于不同位置的每对元素按位 与（AND）运算的结果等于 0 ，则称该子数组为优雅子数组。

返回最长的优雅子数组的长度。

子数组 是数组中的一个连续部分。

注意：长度为 1 的子数组始终视作优雅子数组。

示例 1：

输入：nums = [1,3,8,48,10]
输出：3
解释：最长的优雅子数组是 [3,8,48] 。子数组满足题目条件：
- 3 AND 8 = 0
- 3 AND 48 = 0
- 8 AND 48 = 0
可以证明不存在更长的优雅子数组，所以返回 3 。

示例 2：

输入：nums = [3,1,5,11,13]
输出：1
解释：最长的优雅子数组长度为 1 ，任何长度为 1 的子数组都满足题目条件。

提示：

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

方法一：双指针 · Go 实现

思考

枚举全部子数组再检查两两按位与是否为 $0$ ，子数组有 $O (n^{2})$ 个， $n \leq 10^{5}$ 无法通过。对每个右端点向左扫描，最坏仍是平方级。

「任意两数按位与为 $0$ 」等价于各数置 $1$ 的二进制位互不重叠，因此窗口内所有数的按位或即可作为占用位集合。窗口一旦与新元素冲突，必须从左侧移出元素直至冲突消失，故左端点单调右移。

用 $mask$ 维护窗口按位或，右指针扫描；冲突时用异或撤销左端元素。每个下标进出窗口至多一次，即可在线性时间内得到最长合法窗口。

根据题目描述，子数组的每个元素的二进制位上的 $1$ 的位置不能相同，这样才能保证任意两个元素的按位与结果为 $0$ 。

因此，我们可以使用双指针 $l$ 和 $r$ 维护一个滑动窗口，使得窗口内的元素满足题目条件。

我们用一个变量 $mask$ 来表示窗口内的元素的按位或的结果，接下来，遍历数组的每个元素。对于当前元素 $x$ ，如果 $mask$ 和 $x$ 的按位与结果不为 $0$ ，说明当前元素 $x$ 与窗口内的元素有重复的二进制位，此时需要移动左指针 $l$ ，直到 $mask$ 和 $x$ 的按位与结果为 $0$ 。然后，我们将 $mask$ 和 $x$ 的按位或的结果赋值给 $mask$ ，并更新答案 $ans = max (ans, r - l + 1)$ 。

遍历结束后，返回答案 $ans$ 即可。

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

func longestNiceSubarray(nums []int) (ans int) {
	mask, l := 0, 0
	for r, x := range nums {
		for mask&x != 0 {
			mask ^= nums[l]
			l++
		}
		mask |= x
		ans = max(ans, r-l+1)
	}
	return
}

力扣原题 · Doocs 题解来源

2444. 统计定界子数组的数目

困难1 种解法

标签：队列、数组、滑动窗口、单调队列

题目、示例与约束

给你一个整数数组 nums 和两个整数 minK 以及 maxK 。

nums 的定界子数组是满足下述条件的一个子数组：

子数组中的 最小值 等于 minK 。
子数组中的 最大值 等于 maxK 。

返回定界子数组的数目。

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [1,3,5,2,7,5], minK = 1, maxK = 5
输出：2
解释：定界子数组是 [1,3,5] 和 [1,3,5,2] 。

示例 2：

输入：nums = [1,1,1,1], minK = 1, maxK = 1
输出：10
解释：nums 的每个子数组都是一个定界子数组。共有 10 个子数组。

提示：

2 <= nums.length <= 10⁵
1 <= nums[i], minK, maxK <= 10⁶

方法一：枚举右端点 · Go 实现

思考

$n \leq 10^{5}$ ，定界子数组要求元素落在 $[minK, maxK]$ 且两端极值都出现。以右端 $i$ 统计时，左端必须晚于最近的越界位置，且不晚于最近的 $minK$ 与 $maxK$ 中较左者。

维护越界下标 $k$ 以及 $j_{1}$ 、 $j_{2}$ ，答案累加 $max (0, min (j_{1}, j_{2}) - k)$ 。每个右端 $O (1)$ 。

由题意，我们可以知道，定界子数组的所有元素都在区间 $[minK, maxK]$ 中，且最小值一定为 $minK$ ，最大值一定为 $maxK$ 。

我们遍历数组 $nums$ ，统计以 $nums [i]$ 为右端点的定界子数组的个数，然后将所有的个数相加即可。

具体实现逻辑如下：

维护最近一个不在区间 $[minK, maxK]$ 中的元素的下标 $k$ ，初始值为 $- 1$ 。那么当前元素 $nums [i]$ 的左端点一定大于 $k$ 。
维护最近一个值为 $minK$ 的下标 $j_{1}$ ，最近一个值为 $maxK$ 的下标 $j_{2}$ ，初始值均为 $- 1$ 。那么当前元素 $nums [i]$ 的左端点一定小于等于 $min (j_{1}, j_{2})$ 。
综上可知，以当前元素为右端点的定界子数组的个数为 $max (0, min (j_{1}, j_{2}) - k)$ 。累加所有的个数即可。

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

func countSubarrays(nums []int, minK int, maxK int) int64 {
	ans := 0
	j1, j2, k := -1, -1, -1
	for i, v := range nums {
		if v < minK || v > maxK {
			k = i
		}
		if v == minK {
			j1 = i
		}
		if v == maxK {
			j2 = i
		}
		ans += max(0, min(j1, j2)-k)
	}
	return int64(ans)
}

力扣原题 · Doocs 题解来源

2461. 长度为 K 子数组中的最大和

中等1 种解法

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

题目、示例与约束

给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：

子数组的长度是 k，且
子数组中的所有元素 各不相同。

返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。

子数组 是数组中一段连续非空的元素序列。

示例 1：

输入：nums = [1,5,4,2,9,9,9], k = 3
输出：15
解释：nums 中长度为 3 的子数组是：
- [1,5,4] 满足全部条件，和为 10 。
- [5,4,2] 满足全部条件，和为 11 。
- [4,2,9] 满足全部条件，和为 15 。
- [2,9,9] 不满足全部条件，因为元素 9 出现重复。
- [9,9,9] 不满足全部条件，因为元素 9 出现重复。
因为 15 是满足全部条件的所有子数组中的最大子数组和，所以返回 15 。

示例 2：

输入：nums = [4,4,4], k = 3
输出：0
解释：nums 中长度为 3 的子数组是：
- [4,4,4] 不满足全部条件，因为元素 4 出现重复。
因为不存在满足全部条件的子数组，所以返回 0 。

提示：

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

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

思考

定长 $k$ 且元素互异的子数组最大和， $n \leq 10^{5}$ 。滑动窗口维护和与频次表：窗口内不同元素个数等于 $k$ 时更新答案。右端纳入、左端弹出，弹出后次数为 $0$ 则删键。

我们维护一个长度为 $k$ 的滑动窗口，用哈希表 $c n t$ 记录窗口中每个数字出现的次数，用变量 $s$ 记录窗口中所有数字的和。每次滑动窗口，如果窗口中的数字都不重复，那么更新答案。

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

func maximumSubarraySum(nums []int, k int) (ans int64) {
	n := len(nums)
	cnt := map[int]int64{}
	var s int64
	for _, x := range nums[:k] {
		cnt[x]++
		s += int64(x)
	}
	if len(cnt) == k {
		ans = s
	}
	for i := k; i < n; i++ {
		cnt[nums[i]]++
		cnt[nums[i-k]]--
		if cnt[nums[i-k]] == 0 {
			delete(cnt, nums[i-k])
		}
		s += int64(nums[i] - nums[i-k])
		if len(cnt) == k && ans < s {
			ans = s
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2516. 每种字符至少取 K 个

中等1 种解法

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

题目、示例与约束

给你一个由字符 'a'、'b'、'c' 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。

你必须取走每种字符至少 k 个，返回需要的最少分钟数；如果无法取到，则返回 -1 。

示例 1：

输入：s = "aabaaaacaabc", k = 2
输出：8
解释：
从 s 的左侧取三个字符，现在共取到两个字符 'a' 、一个字符 'b' 。
从 s 的右侧取五个字符，现在共取到四个字符 'a' 、两个字符 'b' 和两个字符 'c' 。
共需要 3 + 5 = 8 分钟。
可以证明需要的最少分钟数是 8 。

示例 2：

输入：s = "a", k = 1
输出：-1
解释：无法取到一个字符 'b' 或者 'c'，所以返回 -1 。

提示：

1 <= s.length <= 10⁵
s 仅由字母 'a'、'b'、'c' 组成
0 <= k <= s.length

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

思考

每次只能从当前串的左端或右端取走一个字符，要使 $a, b, c$ 各至少取到 $k$ 个，并最小化取走次数。枚举左右各取多少在 $n \leq 10^{5}$ 下为平方级。

取走的是一段前缀加一段后缀，留下的是中间一个窗口。等价于在剩余字符中每种仍不少于 $k$ 的前提下最大化窗口。先统计全串频次，不足则无解；再滑动窗口扩大右端、在某种字符不足 $k$ 时收缩左端，最长合法窗口对应最少取走长度。

我们先用哈希表或者一个长度为 $3$ 的数组 $c n t$ 统计字符串 $s$ 中每个字符的个数，如果有字符的个数小于 $k$ 个，则无法取到，提前返回 $- 1$ 。

题目要我们在字符串左侧以及右侧取走字符，最终取到的每种字符的个数都不少于 $k$ 个。我们不妨反着考虑问题，取走中间某个窗口大小的字符串，使得剩下的两侧字符串中，每种字符的个数都不少于 $k$ 个。

因此，我们维护一个滑动窗口，用指针 $j$ 和 $i$ 分别表示窗口的左右边界，窗口内的字符串是我们要取走的。我们每一次移动右边界 $i$ ，将对应的字符 $s [i]$ 加入到窗口中（也即取走一个字符 $s [i]$ ），此时如果 $c n t [s [i]]$ 个数小于 $k$ ，那么我们循环移动左边界 $j$ ，直到 $c n t [s [i]]$ 个数不小于 $k$ 为止。此时的窗口大小为 $i - j + 1$ ，更新最大窗口。

最终的答案就是字符串 $s$ 的长度减去最大窗口的大小。

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

func takeCharacters(s string, k int) int {
	cnt := [3]int{}
	for _, c := range s {
		cnt[c-'a']++
	}
	for _, x := range cnt {
		if x < k {
			return -1
		}
	}
	mx, j := 0, 0
	for i, c := range s {
		c -= 'a'
		for cnt[c]--; cnt[c] < k; j++ {
			cnt[s[j]-'a']++
		}
		mx = max(mx, i-j+1)
	}
	return len(s) - mx
}

力扣原题 · Doocs 题解来源

2524. 子数组的最大频率分数 🔒

困难1 种解法

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

题目、示例与约束

给定一个整数数组 nums 和一个正整数 k 。

数组的 频率得分 是数组中不同值的幂次之和，并将和对 10⁹ + 7 取模。

例如，数组 [5,4,5,7,4,4] 的频率得分为 (4³ + 5² + 7¹) modulo (10⁹ + 7) = 96 。

返回 nums 中长度为 k 的 子数组 的最大频率得分。你需要返回取模后的最大值，而不是实际值。

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

示例 1 ：

输入：nums = [1,1,1,2,1,2], k = 3
输出：5
解释：子数组 [2,1,2] 的频率分数等于 5。可以证明这是我们可以获得的最大频率分数。

示例 2 ：

输入：nums = [1,1,1,1,1,1], k = 4
输出：1
解释：所有长度为 4 的子数组的频率得分都等于 1。

提示：

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

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

思考

定长 $k$ 窗口的分数是 $\sum x^{freq (x)} mod (10^{9} + 7)$ ，要求所有窗口的最大分数。每个窗口从头计算需对频次做快速幂，窗口数为 $n - k + 1$ 时偏慢。

相邻窗口只进一个元素、出一个元素。用哈希表维护频次，分数按 $x^{c + 1} - x^{c} = (x - 1) x^{c}$ 增量更新（新出现则加 $x$ ，频次降到 $0$ 则减 $x$ ）。进出相同则分数不变。

我们用哈希表 $cnt$ 维护窗口大小为 $k$ 的元素及其出现的次数。

先算出初始窗口为 $k$ 的所有元素的分数。然后利用滑动窗口，每次加入一个元素，并移除最左边的元素，同时利用快速幂更新分数。

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

func maxFrequencyScore(nums []int, k int) int {
	cnt := map[int]int{}
	for _, v := range nums[:k] {
		cnt[v]++
	}
	cur := 0
	const mod int = 1e9 + 7
	qpow := func(a, n int) int {
		ans := 1
		for ; n > 0; n >>= 1 {
			if n&1 == 1 {
				ans = ans * a % mod
			}
			a = a * a % mod
		}
		return ans
	}
	for k, v := range cnt {
		cur = (cur + qpow(k, v)) % mod
	}
	ans := cur
	for i := k; i < len(nums); i++ {
		a, b := nums[i-k], nums[i]
		if a != b {
			if cnt[b] > 0 {
				cur += (b - 1) * qpow(b, cnt[b]) % mod
			} else {
				cur += b
			}
			if cnt[a] > 1 {
				cur -= (a - 1) * qpow(a, cnt[a]-1) % mod
			} else {
				cur -= a
			}
			cur = (cur + mod) % mod
			ans = max(ans, cur)
			cnt[b]++
			cnt[a]--
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2537. 统计好子数组的数目

中等1 种解法

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

题目、示例与约束

给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中好子数组的数目。

一个子数组 arr 如果有至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个好子数组。

子数组 是原数组中一段连续非空的元素序列。

示例 1：

输入：nums = [1,1,1,1,1], k = 10
输出：1
解释：唯一的好子数组是这个数组本身。

示例 2：

输入：nums = [3,1,4,3,2,2,4], k = 2
输出：4
解释：总共有 4 个不同的好子数组：
- [3,1,4,3,2,2] 有 2 对。
- [3,1,4,3,2,2,4] 有 3 对。
- [1,4,3,2,2,4] 有 2 对。
- [4,3,2,2,4] 有 2 对。

提示：

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

方法一：哈希表 + 双指针 · Go 实现

思考

子数组“好”当且仅当其中相同元素对不少于 $k$ 。枚举左右端点再统计对数是立方或平方级， $n \leq 10^{5}$ 不可行。

对数随窗口增大而单调不减。右端点右移时，新元素 $x$ 贡献已有的 $cnt [x]$ 对。左端点尽量右移，只要移出后对数仍至少为 $k$ 。此时 $[0, i]$ 都可作为左端，答案加上 $i + 1$ 。

如果一个子数组中包含 $k$ 对相同的元素，那么这个子数组一定包含至少 $k$ 对相同的元素。

我们用一个哈希表 $cnt$ 统计窗口内数组元素出现的次数，用 $cur$ 统计窗口内相同元素的对数，用 $i$ 维护窗口的左端点。

遍历数组 $nums$ ，我们将当前元素 $x$ 作为右端点，那么窗口内相同元素的对数将增加 $cnt [x]$ ，同时将 $x$ 的出现次数加一，即 $cnt [x] \leftarrow cnt [x] + 1$ 。接下来，我们循环判断移出左端点后窗口内相同元素的对数是否大于等于 $k$ ，如果大于等于 $k$ ，那么我们将左端点元素的出现次数减一，即 $cnt [nums [i]] \leftarrow cnt [nums [i]] - 1$ ，同时将窗口内相同元素的对数减去 $cnt [nums [i]]$ ，即 $cur \leftarrow cur - cnt [nums [i]]$ ，同时将左端点右移，即 $i \leftarrow i + 1$ 。此时窗口左端点以及左侧的所有元素都可以作为当前右端点的左端点，因此答案加上 $i + 1$ 。

最后，我们返回答案即可。

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

func countGood(nums []int, k int) int64 {
	cnt := map[int]int{}
	ans, cur := 0, 0
	i := 0
	for _, x := range nums {
		cur += cnt[x]
		cnt[x]++
		for cur-cnt[nums[i]]+1 >= k {
			cnt[nums[i]]--
			cur -= cnt[nums[i]]
			i++
		}
		if cur >= k {
			ans += i + 1
		}
	}
	return int64(ans)
}

力扣原题 · Doocs 题解来源

2653. 滑动子数组的美丽值

中等2 种解法

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

题目、示例与约束

给你一个长度为 n 的整数数组 nums ，请你求出每个长度为 k 的子数组的 美丽值 。

一个子数组的 美丽值 定义为：如果子数组中第 x 小整数 是负数，那么美丽值为第 x 小的数，否则美丽值为 0 。

请你返回一个包含 n - k + 1 个整数的数组，依次表示数组中从第一个下标开始，每个长度为 k 的子数组的 美丽值 。

子数组指的是数组中一段连续非空的元素序列。

示例 1：

输入：nums = [1,-1,-3,-2,3], k = 3, x = 2
输出：[-1,-2,-2]
解释：总共有 3 个 k = 3 的子数组。
第一个子数组是 [1, -1, -3] ，第二小的数是负数 -1 。
第二个子数组是 [-1, -3, -2] ，第二小的数是负数 -2 。
第三个子数组是 [-3, -2, 3] ，第二小的数是负数 -2 。

示例 2：

输入：nums = [-1,-2,-3,-4,-5], k = 2, x = 2
输出：[-1,-2,-3,-4]
解释：总共有 4 个 k = 2 的子数组。
[-1, -2] 中第二小的数是负数 -1 。
[-2, -3] 中第二小的数是负数 -2 。
[-3, -4] 中第二小的数是负数 -3 。
[-4, -5] 中第二小的数是负数 -4 。

示例 3：

输入：nums = [-3,1,2,-3,0,-3], k = 2, x = 1
输出：[-3,0,-3,-3,-3]
解释：总共有 5 个 k = 2 的子数组。
[-3, 1] 中最小的数是负数 -3 。
[1, 2] 中最小的数不是负数，所以美丽值为 0 。
[2, -3] 中最小的数是负数 -3 。
[-3, 0] 中最小的数是负数 -3 。
[0, -3] 中最小的数是负数 -3 。

提示：

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

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

思考

窗口第 $x$ 小若为负则输出该值，否则 $0$ 。值域仅 $[- 50, 50]$ ，不必对每个窗口排序。 $n \leq 10^{5}$ 时 $O (n k \log k)$ 偏紧。

用长度 $101$ 的计数数组维护窗口，查询时从负数一侧累加计数，首次达到 $x$ 即第 $x$ 小；若全非负则返回 $0$ 。

我们注意到，数组 $n u m s$ 中元素的范围为 $[- 50, 50]$ ，因此，我们可以用一个数组长度为 $101$ 的数组 $c n t$ 统计 $[- 50, 50]$ 中每个数出现的次数。由于负数的存在，我们可以将每个数加上 $50$ ，使得每个数都变成非负数，这样就可以用数组 $c n t$ 统计每个数出现的次数了。

接下来，我们遍历数组 $n u m s$ ，维护一个长度为 $k$ 的滑动窗口，窗口中所有元素出现的次记数录在数组 $c n t$ 中，然后我们遍历数组 $c n t$ ，找到第 $x$ 小的负数，即为当前滑动窗口的美丽值。如果不存在第 $x$ 小的负数，那么美丽值为 $0$ 。

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

func getSubarrayBeauty(nums []int, k int, x int) []int {
	n := len(nums)
	cnt := [101]int{}
	for _, x := range nums[:k] {
		cnt[x+50]++
	}
	ans := make([]int, n-k+1)
	f := func(x int) int {
		s := 0
		for i := 0; i < 50; i++ {
			s += cnt[i]
			if s >= x {
				return i - 50
			}
		}
		return 0
	}
	ans[0] = f(x)
	for i, j := k, 1; i < n; i, j = i+1, j+1 {
		cnt[nums[i]+50]++
		cnt[nums[i-k]+50]--
		ans[j] = f(x)
	}
	return ans
}

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

思考

方法一依赖狭小值域。对偶堆把较小的 $x$ 个数放在大根堆一侧，堆顶即候选美丽值，再以延迟删除处理滑出窗口的元素。

值域更大时仍可 $O (n \log k)$ 维护第 $x$ 小，本题作为对计数法的结构替换。

我们可以使用两个优先队列（大小根堆）维护当前窗口中的元素，其中一个优先队列存储当前窗口中较小的 $x$ 个元素，另一个优先队列存储当前窗口中较大的 $k - x$ 个元素。我们还需要一个延迟删除字典 delayed，用于记录当前窗口中的元素是否需要删除。

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

add_num(num)：将 num 加入当前窗口中。
find()：返回当前窗口的美丽值。
remove_num(num)：将 num 从当前窗口中移除。
prune(pq)：如果堆顶元素在延迟删除字典 delayed 中，则将其从堆顶弹出，并从该元素的延迟删除次数中减一。如果该元素的延迟删除次数为零，则将其从延迟删除字典中删除。
rebalance()：平衡两个优先队列的大小。

在 add_num(num) 方法中，我们先考虑将 num 加入较小的队列中，如果数量大于 $x$ 或者 num 小于等于较小的队列的堆顶元素，则将 num 加入较小的队列中；否则，将 num 加入较大的队列中。然后我们调用 rebalance() 方法，使得较小的队列中的元素数量不超过 $x$ 。

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

在 find() 方法中，如果较小的队列的大小等于 $x$ ，则返回较小的队列的堆顶元素，否则返回 $0$ 。

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

在 rebalance() 方法中，如果较小的队列的大小大于 $x$ ，则将较小的队列的堆顶元素加入较大的队列中，并调用 prune() 方法，使得较小的队列的堆顶元素不在延迟删除字典中。如果较小的队列的大小小于 $x$ 且较大的队列的大小大于 $0$ ，则将较大的队列的堆顶元素加入较小的队列中，并调用 prune() 方法，使得较大的队列的堆顶元素不在延迟删除字典中。

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

相似题目：

480. 滑动窗口中位数

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

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

func (this *MedianFinder) AddNum(num int) {
	if this.smallSize < this.x || 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) Find() int {
	if this.smallSize == this.x {
		return -this.small.IntSlice[0]
	}
	return 0
}

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.x {
		heap.Push(&this.large, -heap.Pop(&this.small).(int))
		this.smallSize--
		this.largeSize++
		this.prune(&this.small)
	} else if this.smallSize < this.x && this.largeSize > 0 {
		heap.Push(&this.small, -heap.Pop(&this.large).(int))
		this.smallSize++
		this.largeSize--
		this.prune(&this.large)
	}
}

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
}

func getSubarrayBeauty(nums []int, k int, x int) []int {
	finder := Constructor(x)
	for _, num := range nums[:k] {
		if num < 0 {
			finder.AddNum(num)
		}
	}
	ans := []int{finder.Find()}
	for i := k; i < len(nums); i++ {
		if nums[i] < 0 {
			finder.AddNum(nums[i])
		}
		if nums[i-k] < 0 {
			finder.RemoveNum(nums[i-k])
		}
		ans = append(ans, finder.Find())
	}
	return ans
}

力扣原题 · Doocs 题解来源

2730. 找到最长的半重复子字符串

中等2 种解法

标签：字符串、滑动窗口

题目、示例与约束

给你一个下标从 0 开始的字符串 s ，这个字符串只包含 0 到 9 的数字字符。

如果一个字符串 t 中至多有一对相邻字符是相等的，那么称这个字符串 t 是 半重复的 。例如，"0010" 、"002020" 、"0123" 、"2002" 和 "54944" 是半重复字符串，而 "00101022" （相邻的相同数字对是 00 和 22）和 "1101234883" （相邻的相同数字对是 11 和 88）不是半重复字符串。

请你返回 s 中最长 半重复 子字符串的长度。

示例 1：

输入：s = "52233"

输出：4

解释：

最长的半重复子字符串是 "5223"。整个字符串 "52233" 有两个相邻的相同数字对 22 和 33，但最多只能选取一个。

示例 2：

输入：s = "5494"

输出：4

解释：

s 是一个半重复字符串。

示例 3：

输入：s = "1111111"

输出：2

解释：

最长的半重复子字符串是 "11"。子字符串 "111" 有两个相邻的相同数字对，但最多允许选取一个。

提示：

1 <= s.length <= 50
'0' <= s[i] <= '9'

方法一：双指针 · Go 实现

思考

半重复串至多有一对相邻相同字符，求最长长度。枚举左右端点再检查相邻对，在 $n \leq 10^{5}$ 时不可行。

右端点右移时累计相邻相等的次数；次数超过 $1$ 则左端点右移直至合法。窗口内始终最多一对重复，长度的最大值即为答案。

我们用双指针维护一个区间 $s [j . . i]$ ，使得区间内最多只有一个相邻字符相等，初始时 $j = 0$ , $i = 1$ 。初始化答案 $a n s = 1$ 。

我们用 $c n t$ 记录区间内相邻字符相等的个数，如果 $c n t > 1$ ，那么我们就需要移动左指针 $j$ ，直到 $c n t \leq 1$ 。每一次，我们更新答案为 $a n s = max (a n s, i - j + 1)$ 。

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

func longestSemiRepetitiveSubstring(s string) (ans int) {
	ans = 1
	for i, j, cnt := 1, 0, 0; i < len(s); i++ {
		if s[i] == s[i-1] {
			cnt++
		}
		for ; cnt > 1; j++ {
			if s[j] == s[j+1] {
				cnt--
			}
		}
		ans = max(ans, i-j+1)
	}
	return
}

方法二：双指针（优化） · Go 实现

思考

方法一在窗口不合法时可能连续收缩并维护全局最大。题目只要最长长度，每次越界只需把左端点右移一格，窗口长度单调不减，最后用 $n - l$ 即得最长合法窗口。

由于题目只需要我们找到最长的半重复子字符串的长度，因此，每次当区间内相邻字符相等的个数超过 $1$ 时，我们可以只移动左指针 $l$ 一次，右指针 $r$ 继续向右移动。这样可以保证子字符串的长度不会减小。

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

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

func longestSemiRepetitiveSubstring(s string) (ans int) {
	cnt, l := 0, 0
	for i, c := range s[1:] {
		if byte(c) == s[i] {
			cnt++
		}
		if cnt > 1 {
			if s[l] == s[l+1] {
				cnt--
			}
			l++
		}
	}
	return len(s) - l
}

力扣原题 · Doocs 题解来源

LeetCode Go · 滑动窗口（2） ​

1343. 大小为 K 且平均值大于等于阈值的子数组数目 ​

1358. 包含所有三种字符的子字符串数目 ​

1423. 可获得的最大点数 ​

1438. 绝对差不超过限制的最长连续子数组 ​

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

1499. 满足不等式的最大值 ​

1610. 可见点的最大数目 ​

1652. 拆炸弹 ​

1695. 删除子数组的最大得分 ​

1763. 最长的美好子字符串 ​

1839. 所有元音按顺序排布的最长子字符串 ​

1852. 每个子数组的数字种类数 🔒 ​

1876. 长度为三且各字符不同的子字符串 ​

1984. 学生分数的最小差值 ​

2067. 等计数子串的数量 🔒 ​

2090. 半径为 k 的子数组平均值 ​

2107. 分享 K 个糖果后独特口味的数量 🔒 ​

2134. 最少交换次数来组合所有的 1 II ​

2156. 查找给定哈希值的子串 ​

2260. 必须拿起的最小连续卡牌数 ​

2269. 找到一个数字的 K 美丽值 ​

2379. 得到 K 个黑块的最少涂色次数 ​

2401. 最长优雅子数组 ​

2444. 统计定界子数组的数目 ​

2461. 长度为 K 子数组中的最大和 ​

2516. 每种字符至少取 K 个 ​

2524. 子数组的最大频率分数 🔒 ​

2537. 统计好子数组的数目 ​

2653. 滑动子数组的美丽值 ​

2730. 找到最长的半重复子字符串 ​

继续阅读

LeetCode Go · 滑动窗口（2）

1343. 大小为 K 且平均值大于等于阈值的子数组数目

1358. 包含所有三种字符的子字符串数目

1423. 可获得的最大点数

1438. 绝对差不超过限制的最长连续子数组

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

1499. 满足不等式的最大值

1610. 可见点的最大数目

1652. 拆炸弹

1695. 删除子数组的最大得分

1763. 最长的美好子字符串

1839. 所有元音按顺序排布的最长子字符串

1852. 每个子数组的数字种类数 🔒

1876. 长度为三且各字符不同的子字符串

1984. 学生分数的最小差值

2067. 等计数子串的数量 🔒

2090. 半径为 k 的子数组平均值

2107. 分享 K 个糖果后独特口味的数量 🔒

2134. 最少交换次数来组合所有的 1 II

2156. 查找给定哈希值的子串

2260. 必须拿起的最小连续卡牌数

2269. 找到一个数字的 K 美丽值

2379. 得到 K 个黑块的最少涂色次数

2401. 最长优雅子数组

2444. 统计定界子数组的数目

2461. 长度为 K 子数组中的最大和

2516. 每种字符至少取 K 个

2524. 子数组的最大频率分数 🔒

2537. 统计好子数组的数目

2653. 滑动子数组的美丽值

2730. 找到最长的半重复子字符串