php – 解密系列 – 找到连续整数序列的数量,使得它们的和为零

您将获得一系列N个整数.任务是找到连续的整数序列的数量,使得它们的和为零.

例如,如果序列是：
2,-2,6,-6,8
有3个这样的序列：

>’2,-2′
>’6,-6′
>’2,-6′

我已经有了用PHP编写的以下程序,它读取STDIN的输入(第一行包含后面的整数数.)

<?php

$n = fgets(STDIN) * 1;
$seq = array();

for ($i = 0; $i < $n; $i++) {
    $seq[] = fgets( STDIN ) * 1;
}

$count = 0;
for( $i = 0; $i < $n; $i++)
{
    $number = 0;
    for( $j = $i; $j < $n; $j++)
    {
        $number += $seq[$j];
        if( $number == 0 )
            $count++;
    }
}

echo 'count: ' . $count . PHP_EOL;

输入示例

5
2
-2
6
-6
8

这适用于较小的序列,但其效率为O(n ^ 2).

对于包含100.000个整数的序列,什么算法适合 – 可能有O(n)效率？