难度: Easy
Submission
运行时间: 36 ms
内存: 26.8 MB
class Solution:
def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:
n = len(calories)
cumsum = [0] * (n + k)
for i in range(n):
cumsum[i + 1] = cumsum[i] + calories[i]
score = 0
for i in range(n - k + 1):
T = cumsum[i + k] - cumsum[i]
if T < lower:
score -= 1
elif T > upper:
score += 1
return score
Explain
本题解采用滑动窗口和前缀和的方法来解决问题。首先计算出所有卡路里的前缀和数组 cumsum，其中 cumsum[i] 表示从开始到第 i-1 个元素的卡路里总和。这样，任意长度为 k 的子数组的卡路里和可以通过 cumsum[i+k] - cumsum[i] 快速计算得出，避免了重复计算。接着，遍历数组，对于每个长度为 k 的连续子数组，比较其卡路里总和与给定的 lower 和 upper 值，根据比较结果更新得分。如果总和小于 lower，则将 score 减一，如果大于 upper，则将 score 加一。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:
n = len(calories)
# 创建前缀和数组，长度为 n+k 为了方便计算
cumsum = [0] * (n + k)
# 计算前缀和
for i in range(n):
cumsum[i + 1] = cumsum[i] + calories[i]
score = 0
# 遍历每个长度为 k 的子数组
for i in range(n - k + 1):
# 计算当前子数组的卡路里总和
T = cumsum[i + k] - cumsum[i]
# 根据卡路里总和更新得分
if T < lower:
score -= 1
elif T > upper:
score += 1
return score
Explore
在题解中，前缀和数组的长度错误地设置为 `n + k`，实际上这是不必要的。前缀和数组的长度应当只需要为 `n + 1`，这是为了保证能够包括从第0个元素到第n-1个元素的所有前缀和，且使用从1开始的索引方式来方便计算。设置为 `n + k` 可能是对其他类型问题的通用处理误用，或者是错误，因为在这个特定问题中我们只需要计算到 `cumsum[n]`，即从第0个元素到最后一个元素的总和。
该表达式的正确性基于前缀和数组的定义，即 `cumsum[i]` 表示从数组开始到第i-1个元素的卡路里总和。因此，`cumsum[i + k]` 表示从数组开始到第i+k-1个元素的总和。当我们计算 `cumsum[i + k] - cumsum[i]` 时，实际上得到的是第i个元素到第i+k-1个元素的总和，即长度为k的子数组的卡路里总和。这个计算是基于索引从0开始连续的数组序列这一假设。
在前缀和数组中，`cumsum[0]` 被初始化为0是为了方便计算任意子区间的和，包括从数组第一个元素开始的区间。从索引1开始计算是因为，`cumsum[1]` 代表第一个元素的值，`cumsum[2]` 代表第一个和第二个元素的总和，依此类推。这种初始化方式使得任何从第i个到第j个元素的子数组和都可以简单地通过 `cumsum[j+1] - cumsum[i]` 来计算，其中i和j是基于0的索引。
如果数组 `calories` 的长度小于 k，那么根据题目逻辑，不存在长度为 k 的子数组，因此不能形成一个有效的评估窗口来比较与 lower 和 upper 的值。在这种情况下，可以直接返回得分为0，因为没有任何子数组可以用来评估得分。这应该在算法实现的开始部分进行检查，如果 `n < k`，直接返回0。