带限制条件的最大子数组和（限制子数组必须包含至少k个元素） 题目描述 给定一个整数数组 nums 和一个整数 k （ k ≥ 1 ），要求找到一个连续子数组，使得该子数组的和最大，并且子数组的长度至少为 k 。例如，对于 nums = [1, 2, 3, -4, 5] ， k = 2 ，最大和为 1 + 2 + 3 = 6 （子数组 [1, 2, 3] 长度为 3 ≥ 2）。 解题过程 问题分析 如果没有长度限制，最大子数组和问题可以通过 Kadane 算法在 O(n) 时间内解决。但加入长度至少为 k 的限制后，需要确保候选子数组满足长度要求。暴力解法枚举所有长度 ≥ k 的子数组，时间复杂度为 O(n²)，不够高效。我们需要一种 O(n) 或 O(n log n) 的解法。 关键思路 设 prefix[i] 表示前 i 个元素的前缀和（ prefix[0] = 0 ， prefix[i] = nums[0] + ... + nums[i-1] ）。 对于以 i 结尾且长度至少为 k 的子数组，其和为 prefix[i+1] - prefix[j] ，其中 j ≤ i - k + 1 （子数组从 j 开始到 i ，长度至少为 k ）。 要最大化这个和，只需固定 i ，找到 j ∈ [0, i-k+1] 使得 prefix[j] 最小。这可以通过遍历时维护一个最小值来实现。 算法步骤 计算前缀和数组 prefix 。 初始化 min_prefix = prefix[0] ， max_sum = -∞ 。 遍历 i 从 k 到 n （因为长度至少为 k ，所以 i 从 k 开始）： 更新 min_prefix = min(min_prefix, prefix[i - k]) （注意 i-k 确保子数组长度 ≥ k）。 当前候选和 sum = prefix[i] - min_prefix 。 更新 max_sum = max(max_sum, sum) 。 返回 max_sum 。 示例演示 以 nums = [1, 2, 3, -4, 5] ， k = 2 为例： prefix = [0, 1, 3, 6, 2, 7] （长度 n+1=6）。 i = 2 ： min_prefix = min(prefix[0]) = 0 ， sum = prefix[2] - 0 = 3 ， max_sum = 3 。 i = 3 ： min_prefix = min(0, prefix[1]=1) = 0 ， sum = 6 - 0 = 6 ， max_sum = 6 。 i = 4 ： min_prefix = min(0, 1, prefix[2]=3) = 0 ， sum = 2 - 0 = 2 ， max_sum = 6 。 i = 5 ： min_prefix = min(0, 1, 3, prefix[3]=6) = 0 ， sum = 7 - 0 = 7 ，但注意子数组 [5] 长度仅为 1，不符合要求？这里 i=5 对应子数组从 j=5-2=3 开始（即 nums[3] 到 nums[4] ，和为 -4+5=1 ），但计算的是 prefix[5] - min_prefix = 7 - 0 = 7 ，这实际上对应子数组 [0..4] （整个数组），长度为 5 ≥ 2，和正确为 7。最终结果 max_sum = 7 。 复杂度分析 时间复杂度 O(n)，空间复杂度 O(n)（可优化为 O(1)，只保留必要的前缀和变量）。 总结 通过前缀和和维护最小前缀值，将问题转化为对每个结尾位置 i 寻找最优起始位置 j ，从而在线性时间内解决带长度限制的最大子数组和问题。