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

Question

以下是编程任务.

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

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

• '2,-2'
• '6,-6'
• '2,-2,6,-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)效率？

Answer 1

我们假设您的数据存储在一个数组中,然后就可以了arr.创建一个数组sum,这样:

sum[i] = arr[0] + arr[1] + ... + arr[i]

并且,另外一个开头的单个条目为0(处理从开头开始并总和为零的子数组)

现在,很容易看到,每两个指标i,j,使得i<j和sum[i]=sum[j],连续序列arr[i+1]+arr[i+2]+...+arr[j] = 0.

通过创建此数组sum,您只需要找到有多少重复项.这不能在O(n)¹中完成(这是元素清晰度问题),但可以O(nlogn)使用排序然后迭代和计数来解决,这对于100,000个条目仍然非常快.

请注意,如果有例如n数的重复k阵列中sum,有Choose(n,2) = n(n-1)/2被对这些重复生成的连续子序列.

例:

arr = [1,2,-2,5,6,-6,-5,8]
sum = [0,1,3,1,6,12,6,1,9]
sorted(sum) = [0,1,1,1,3,6,6,9,12]

有3个重复的1和2个重复的6,所以你总共:

Choose(3,2) + Choose(2,2) = 3*2/2 + 2/2 = 3+1 = 4

这确实匹配4个子序列:

2,-2
2,-2,5,6,-6,-5
6,-6
5,6,-6,-5

(1)没有散列,然后你会衰减到O(n ^ 2)最坏的情况,但是会受益于O(n)平均情况,需要O(n)额外的空间.