一个连续子序列(片段)可以由其起始位置 i 和结束位置 j 定义(其中 1≤i≤j≤n)。 根据题意,一个从索引 i 到 j 的片段是“平衡片段”的条件是: ∑k=ijAk=j−i+1 这里的 ∑k=ijAk 是片段中所有水晶的能量和,而 j−i+1 是该片段的长度。
直接暴力枚举所有的起始位置 i 和结束位置 j,然后计算和并判断,时间复杂度会达到 O(n2),对于 n=2×105 的数据规模来说太慢了,会超时。我们需要一个更高效的算法。
多多最近来到了一片神秘的山谷,山谷中散落着一些能量水晶。每一颗水晶拥有一个整数能量值,可能为正,也可能为负。
水晶被排成一条直线,多多决定在其中选择一个连续的水晶序列进行采集。为了保证能量的平衡,他只愿意采集“平衡片段"——即片段中所有水晶的能量值加起来,恰好等于这个片段中水晶的数量。