Python中实现数组重分组：每个分组和至少为10的高效方法

给定数组A = [1,8,2,6,4,8,1,0,1,6,7,3,1,4,9,1,2,1,2,1,1,2]，需要将其拆分为若干子数组，要求每个子数组的元素和至少为10，示例分组结果如下：

子数组列表：[[1,8,2],[6,4],[8,1,0,1],[6,7],[3,1,4,9],[1,2,1,2,1,1,2]]
对应分组和：[11, 10, 10, 13, 17, 10]

实现思路 #

采用贪心策略，从数组头部开始逐个累积元素，一旦当前累积的元素和达到或超过10，就将这组元素作为一个子数组保存，然后重置累积状态继续处理剩余元素。这种方法是线性时间复杂度，效率极高。

Python 代码实现 #

def split_array(arr, min_sum):
    groups = []
    current_group = []
    current_sum = 0
    for num in arr:
        current_group.append(num)
        current_sum += num
        # 满足和的要求时，保存分组并重置
        if current_sum >= min_sum:
            groups.append(current_group)
            current_group = []
            current_sum = 0
    # 处理剩余未分组的元素（题目场景下可省略，增加鲁棒性保留）
    if current_group:
        groups.append(current_group)
    return groups

# 测试示例数组
A = [1,8,2,6,4,8,1,0,1,6,7,3,1,4,9,1,2,1,2,1,1,2]
result_groups = split_array(A, 10)
print("分组结果：", result_groups)
print("分组和：", [sum(group) for group in result_groups])

代码优势 #

• 时间复杂度为O(n)，仅需遍历数组一次，处理效率最优
• 空间复杂度为O(n)，用于存储分组结果，无额外冗余开销
• 逻辑直观，输出结果与示例完全匹配

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