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

Question

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

phpalgorithmperformancesequences

3

以下是一个编程任务。

给定一个由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;

输入示例

这对于较小的序列效果很好，但其效率为O(n^2)。

针对包含100,000个整数的序列，适当的算法是什么 - 可能是O(n)的效率？

- Debreczeni András

2个回答

0

由于我无法回复评论，这是对amit答案的回复。也许我有些错误，但是当将您的方法应用于原始测试用例时，我们没有得到正确的答案：

input = [2, -2, 6, -6, 8]
sum = [2, 0, 6, 0, 8]
sorted(sum) = [0, 0, 2, 6, 8]

由于数字0有2个重复，这给了我们(2*1)/2=1，这是不正确的(正确答案应该是3)。我错过了什么？谢谢。

- mmihaltz

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

假设您的数据存储在一个数组中，让它成为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条目仍非常快。

请注意，如果数组sum中有例如n个数字k的副本，则为这些副本生成了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

如果不进行哈希，最坏情况下时间复杂度会退化为O(n^2)，但平均情况下可以受益于O(n)的时间复杂度，代价是需要额外的O(n)空间。