Maximum Sum Subarray of Size K
你会得到一个整数数组 nums 和一个窗口长度 k。查看每一组恰好包含 k 个相邻元素的序列，并返回其中最大的和。值可能为负数，因此答案也可能是负数。
函数
- numsinteger-array
- 整数数组
- kinteger
- 每个窗口包含多少个相邻元素
- 返回值integer
- 任意 k 个连续元素的最大和
约束条件
1 ≤ k ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 104
示例
- 输入
- nums = [4, -1, 3, 7, -2, 5, 1]k = 3
- 输出
- 10
- 解释
- 长度为 3 的五个窗口的和分别是
6、9、8、10和4。最大的是7 + (-2) + 5 = 10。
- 输入
- nums = [-3, -8, -1, -6]k = 2
- 输出
- -7
- 解释
- 每个值都是负数，因此每个窗口的和也都是负数：
-11、-9和-7。其中最大的是-1 + (-6) = -7。
- 输入
- nums = [5, -2, 4]k = 3
- 输出
- 7
- 解释
- 当
k等于数组的长度时，只有一个窗口，也就是整个数组，并且5 + (-2) + 4 = 7。
进阶
你还能返回最佳窗口的起始位置吗？如果有多个窗口并列，就选最靠左的那个。
提示
逐个打开提示，每个都会多透露一点。
写下两个相邻窗口的和，比如起始索引分别为 0 和 1 的窗口。它们有什么共同点？
它们共享
k-1个元素。窗口向右移动一步时，会增加一个新元素并移除一个旧元素，因此新总和只需在旧总和的基础上进行两次操作即可得到。先把前
k个元素加起来。然后，对于从k到末尾的每个i，加上nums[i]，减去nums[i-k]，并记录遇到的最大和。
题解
共有 n-k+1 个窗口，从头开始累加每个窗口都需要 k 次加法。相邻窗口除了两个元素之外都相同，因此可以滑动窗口，而不是重新计算：一个值进入，一个值离开，每个新总和只需要两次操作。
把每个窗口的数值加起来
结果正确，但无法在最大的测试中运行完毕
思路
窗口由起始位置固定，从索引 0 到 n-k；再往后的起始位置会超出末尾。对于每个起始位置，将 k 个元素相加，并将总和与当前最佳值进行比较。每个窗口都会被检查，因此一定能找到最佳窗口。
计算量为 (n-k+1) × k 次加法；当 k 约为 n 的一半时，计算量最大：当 n = 10^4 且 k = 5000 时，需要 5001 × 5000 次加法，约为 2.5 × 10^7。其中几乎所有加法都重复了前一个窗口中已经完成的计算。
算法
- 将
best设为可能的最小值。 - 对于从
0到n-k的每个起始位置，将total = 0。 - 将
nums[start]到nums[start+k-1]的值加到total中。 - 如果
total大于best，就保存它。 - 返回
best。
def maxSumSubarray(nums, k):
n = len(nums)
best = None
for start in range(n - k + 1):
total = 0
for i in range(start, start + k):
total += nums[i]
if best is None or total > best:
best = total
return best滑动一个固定窗口
思路
在第一个示例中，起始位置为 0 和 1 的窗口的和分别是 6 和 9。两个窗口都包含 -1 和 3，所以第二个窗口的和等于第一个窗口的和，加上移入的 7，再减去移出的 4：6 + 7 - 4 = 9。
每一步都是如此。当右端移动到索引 i 时，nums[i] 移入，nums[i-k] 移出。先计算第一个窗口的和，然后每一步用一次加法和一次减法更新总和，并保留你看到的最大总和。
算法
- 将
nums[0]到nums[k-1]累加到window中。 - 设置
best = window。 - 对于从
k到n-1的每个i，加上nums[i]，再减去nums[i-k]。 - 每一步之后，将
best设置为best和window中较大的那个。 - 返回
best。
def maxSumSubarray(nums, k):
# Sum of the first window, nums[0..k-1].
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
# Slide one step right: nums[i] enters, nums[i-k] leaves.
window += nums[i] - nums[i - k]
best = max(best, window)
return best
易错点和边界情况
- 将
best初始化为0。对于[-3, -8, -1, -6]，当k = 2时，它永远不会被超过，因此返回的是 0，而不是 -7。 - 减去错误的元素。当
nums[i]加入时，离开的是nums[i-k]；使用nums[i-k+1]或nums[i-k-1]会得到长度错误的窗口。 - 过早停止，少处理了一个起点。最后一个窗口从
n-k开始。对于[5, -2, 4]和k = 3，它是唯一的窗口；如果循环边界差 1，就会返回best的初始值。 - 只在循环内比较。对于
[9, 1, 1]，当k = 2时，第一个窗口的值是 10，也是最大值，所以要在循环前将best设为它。
常见问题3
大小为 k 的最大和子数组的时间复杂度是多少？
使用滑动窗口时，时间复杂度为 O(n)，额外空间复杂度为 O(1)：先计算第一个窗口的和，然后每一步进行一次加法和一次减法。分别计算每个窗口的和，时间复杂度为 O(n·k)。
这和最大子数组问题有什么不同？
这里的长度固定为 k，因此滑动求和会覆盖每个候选区间。在最大子数组问题中，长度不固定，Kadane 算法会在每个元素处决定是延续当前子数组，还是重新开始。固定窗口没有这种选择。
前缀和也能解决这个问题吗？
是的。令 prefix[i] 表示前 i 个元素的和；从 s 开始的窗口，其和为 prefix[s+k] - prefix[s]。这种方法的时间复杂度也是 O(n)，但它会存储 n+1 个总和，而滑动窗口只需要两个变量。
def maxSumSubarray(nums, k):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [4, -1, 3, 7, -2, 5, 1] k = 3
预期输出
10