按区间计算累加和的最优方案：0分隔区间内逐次累加15实现方法

该需求的最优解法为单次线性遍历法，时间复杂度为O(n)（n为数组长度），是该需求下的理论最优时间复杂度（必须遍历所有元素至少一次才能完成计算）；如果允许原地修改原数组，额外空间复杂度仅为O(1)，仅需维护一个计数变量即可。

实现逻辑 #

• 初始化计数变量current_step = 0，用于记录当前0分隔区间内的元素偏移量
• 遍历数组每一个元素：
  • 若当前元素为0，重置current_step为0，当前位置直接保留0值
  • 若当前元素为非0值，current_step自增1，当前位置赋值为current_step * 15
• 遍历结束即可直接得到目标数组

代码示例 #

Python 实现（返回新数组，不修改原数组） #

original_arr = [0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,0,1,1,1]
result = []
current_step = 0
for num in original_arr:
    if num == 0:
        current_step = 0
        result.append(0)
    else:
        current_step += 1
        result.append(current_step * 15)

# 验证输出：[0,15,30,45,60,75,0,15,30,45,0,15,30,45,60,0,15,30,45]
print(result)

Python 实现（原地修改数组，空间复杂度O(1)） #

original_arr = [0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,0,1,1,1]
current_step = 0
for idx in range(len(original_arr)):
    if original_arr[idx] == 0:
        current_step = 0
    else:
        current_step += 1
        original_arr[idx] = current_step * 15

方案优势 #

不需要提前切割数组统计所有0分隔区间再做二次计算，仅需一次遍历即可完成所有运算，没有额外的冗余操作，适配任意长度的同规则输入数组。

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