求长度为k的最大和子数组的高效算法（面试题）

暴力枚举所有子数组的方式确实效率低下，时间复杂度是O(nk)——因为每个子数组需要计算k个元素的和，总共n-k+1个子数组。更高效的解法是用滑动窗口法，时间复杂度可以降到O(n)，只需要遍历数组一次。

滑动窗口法的核心思路 #

1. 先计算第一个长度为k的窗口的和，记录当前的最大和以及这个窗口的起始索引。
2. 从第k个元素开始，逐个向右滑动窗口：
   • 新窗口的和 = 前一个窗口的和 - 窗口左端移出的元素 + 窗口右端新加入的元素
   • 每次计算完新窗口的和后，和当前最大和对比，如果更大，就更新最大和以及对应的起始索引。
3. 遍历结束后，根据记录的起始索引，截取数组中长度为k的子数组即可。

代码示例（Python） #

def max_sum_subarray(arr, k):
    n = len(arr)
    if n < k:
        return None  # 处理数组长度小于k的边界情况
    
    # 计算第一个窗口的和
    current_sum = sum(arr[:k])
    max_sum = current_sum
    start_idx = 0
    
    # 滑动窗口遍历剩余元素
    for i in range(k, n):
        current_sum = current_sum - arr[i - k] + arr[i]
        if current_sum > max_sum:
            max_sum = current_sum
            start_idx = i - k + 1
    
    # 返回对应的子数组
    return arr[start_idx:start_idx + k]

# 测试示例
input_arr = [1, -5, 4, 3, 6, 8, 2, 4]
k = 3
print(max_sum_subarray(input_arr, k))  # 输出: [3, 6, 8]

为什么滑动窗口更高效？ #

滑动窗口避免了重复计算子数组的和——暴力法中相邻子数组有k-1个元素是重复的，滑动窗口只需要做一次减法和一次加法就能得到新窗口的和，把每个窗口的计算成本从O(k)降到了O(1)，整体时间复杂度就变成了O(n)。

内容的提问来源于stack exchange，提问作者Tran Phuong