寻找数组中小于k的n个连续元素最大和的高效算法

适用正整数数组的滑动窗口算法（时间复杂度O(n)） #

你之前使用的嵌套循环时间复杂度为O(n²)，数组长度较大时耗时会显著升高。如果数组所有元素均为正整数，滑动窗口是最优解法，思路如下：

• 初始化左指针left = 0，当前窗口和current_sum = 0，符合条件的最大和max_sum = -inf
• 遍历右指针right从0到数组末尾：
  • 将array[right]加到current_sum中
  • 当current_sum >= k时，循环减去array[left]并右移左指针，直到current_sum < k
  • 更新max_sum为max(max_sum, current_sum)
• 最终得到的max_sum就是所求结果

针对你给出的示例，运行过程完全匹配，最终输出结果为6，符合预期。

代码示例（Python） #

def max_sum_less_than_k(array, k):
    left = 0
    current_sum = 0
    max_sum = float('-inf')
    for right in range(len(array)):
        current_sum += array[right]
        while current_sum >= k and left <= right:
            current_sum -= array[left]
            left += 1
        if current_sum > max_sum:
            max_sum = current_sum
    return max_sum

# 测试示例
array = [1, 3, 1, 2, 3, 4, 1]
k = 7
print(max_sum_less_than_k(array, k)) # 输出6

存在负数元素的场景（前缀和+二分，时间复杂度O(nlogn)） #

如果数组包含负数元素，滑动窗口规则不适用，此时可以用前缀和配合二分查找实现：

• 计算数组前缀和数组prefix，其中prefix[i]是前i个元素的和
• 对于每个前缀和prefix[i]，需要找到最小的prefix[j]（j < i）使得prefix[i] - prefix[j] < k，等价于prefix[j] > prefix[i] -k
• 维护一个有序的前缀和集合，每次查找、插入都用二分实现，即可得到符合条件的最大差值

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