Python中结合f与b条件的数组滑动窗口求和优化实现问询

需求说明 #

给定数组 array = [1.0, 1.0, 2.0, 4.0, 1.0]，需实现函数somefunc：

• 参数f：通过检查索引i+f是否有效，决定当前窗口和的分组方向
• 参数b：指定滑动窗口长度，计算从索引i开始的前b个元素的和；若剩余元素不足b个则跳过该索引
• 最终将符合条件的窗口和分别存入两个列表返回

已验证的示例结果：

• somefunc(array,f=1, b=1) 返回 ([1.0, 1.0, 2.0, 4.0], [1.0])
• somefunc(array,f=1, b=2) 返回 ([2.0, 3.0, 6.0], [5.0])
• somefunc(array,f=2, b=2) 返回 ([2.0, 3.0], [6.0, 5.0])

优雅高效的实现方案 #

1. 核心优化思路 #

• 前缀和预处理：预先计算数组的前缀和，让任意窗口的求和操作从O(b)降到O(1)，整体时间复杂度优化为O(n)
• 简洁边界判断：通过数组长度直接推导有效窗口的索引范围，避免冗余的条件嵌套

2. Python代码实现 #

def somefunc(array, f=1, b=1):
    # 构建前缀和数组：prefix[0]=0，prefix[k]对应array前k个元素的和
    prefix = [0.0]
    for num in array:
        prefix.append(prefix[-1] + num)
    
    group1 = []
    group2 = []
    
    # 遍历所有有效窗口的起始索引
    for i in range(len(array) - b + 1):
        # 快速计算当前窗口的和
        window_sum = prefix[i + b] - prefix[i]
        # 根据i+f的有效性分组
        if i + f < len(array):
            group1.append(window_sum)
        else:
            group2.append(window_sum)
    
    return (group1, group2)

3. 验证代码 #

array = [1.0, 1.0, 2.0, 4.0, 1.0]
print(somefunc(array, f=1, b=1))  # 输出符合预期：([1.0, 1.0, 2.0, 4.0], [1.0])
print(somefunc(array, f=1, b=2))  # 输出符合预期：([2.0, 3.0, 6.0], [5.0])
print(somefunc(array, f=2, b=2))  # 输出符合预期：([2.0, 3.0], [6.0, 5.0])

方案优势 #

• 效率更高：前缀和预处理仅需一次遍历，后续窗口求和无重复计算，相比原始迭代实现，当b较大时性能提升明显
• 代码更简洁：通过数组长度直接限定有效索引范围，分组条件直观清晰，避免了复杂的索引嵌套判断

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