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

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) 中完成¹ (这是 element distinctness problem )，但可以在 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]

1 有 3 个重复，6 有 2 个重复，所以你总共有:

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)额外的空间。