难度: Medium
Submission
运行时间: 125 ms
内存: 31.8 MB
class Solution:
def shareCandies(self, candies: List[int], k: int) -> int:
cnt = [0] * 100001
p = 0
for c in candies:
cnt[c] += 1
if cnt[c] == 1: p+=1
for i in range(k):
c = candies[i]
cnt[c] -= 1
if cnt[c] == 0: p -= 1
ans = p
for i in range(k,len(candies)):
out = candies[i-k]
cnt[out] += 1
if cnt[out] == 1: p += 1
in_ = candies[i]
cnt[in_] -= 1
if cnt[in_] == 0: p -= 1
ans = max(ans, p)
return ans
Explain
这个题解主要使用了滑动窗口的方法来解决问题。首先，通过一个固定大小为k的窗口来计算出窗口内独特口味的糖果数量。使用一个数组cnt来记录每种口味糖果的出现次数，同时使用一个变量p来记录当前窗口中独特口味的数量。遍历所有糖果，首先更新cnt数组，当某种口味糖果第一次出现时，p增加1。接着，从第k个糖果开始，每次窗口向右移动一位，移除窗口最左侧的糖果，并添加新的糖果到窗口，同时更新cnt数组和p的值。最后，使用一个变量ans来记录窗口移动过程中p的最大值，即为答案。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def shareCandies(self, candies: List[int], k: int) -> int:
cnt = [0] * 100001 # 初始化计数数组
p = 0 # 初始化独特口味计数
# 计算所有糖果的初始口味计数
for c in candies:
cnt[c] += 1
if cnt[c] == 1: p += 1
# 初始化窗口，移除前k个糖果
for i in range(k):
c = candies[i]
cnt[c] -= 1
if cnt[c] == 0: p -= 1
ans = p # 初始化最大独特口味数
# 滑动窗口，遍历剩余糖果
for i in range(k, len(candies)):
out = candies[i-k] # 移除窗口最左侧糖果
cnt[out] += 1
if cnt[out] == 1: p += 1
in_ = candies[i] # 添加新糖果到窗口
cnt[in_] -= 1
if cnt[in_] == 0: p -= 1
ans = max(ans, p) # 更新最大独特口味数
return ans # 返回结果
Explore
滑动窗口方法在处理固定大小的连续子数组问题时非常有效，主要优势在于它的时间复杂度通常为O(n)，可以通过一次遍历完成计算。同时，这种方法通过更新窗口边界来避免重复计算，使得算法更加高效。对于这类需要计算连续子数组特定属性（如独特元素数量）的问题，滑动窗口提供了一种直观且易于实现的解决方案。
cnt数组的大小设定为100001是基于假设糖果的口味种类可能很多，通常这个数组的大小设置应当覆盖所有可能的糖果口味的值。具体的大小取决于问题描述中糖果口味的可能最大值。如果题目没有明确指出糖果口味的最大值，通常需要根据题目的上下文或示例输入推断。在实际情况下，可根据具体的输入范围调整数组大小以提高空间效率。
确实，题解中的描述有误。按照常规的滑动窗口方法，应该首先通过遍历前k个糖果来初始化窗口内的计数，然后再根据窗口向右移动逐步更新计数和记录结果。题解中提前“移除前k个糖果”的表述可能是指在窗口首次滑动前，对于初始窗口内的糖果进行计数后再开始移动窗口。这应该是对过程描述的一个误导或者表达不清，正常操作应该是初始化后再滑动和调整。