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

发布时间:2022-04-30 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了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)效率?

解决方法

我们假设您的数据存储在一个数组中,并让它成为arr.
创建一个数组总和,这样:

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

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

现在,很容易看出,对于每两个索引i,j使得i element distinctness PRoblem)中完成,但可以使用排序然后迭代和计数在O(nLOGn)中求解,这对于100,000个条目仍然非常快. 和sum>

注意,如果例如在数组和中有数字k的n个重复,则存在为这些重复生成的Choose(n,2)= n(n-1)/ 2个连续子序列.

例:

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

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

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

这确实匹配4个子序列:

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

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

脚本宝典总结

以上是脚本宝典为你收集整理的php – 解密系列 – 找到连续整数序列的数量,使得它们的和为零全部内容,希望文章能够帮你解决php – 解密系列 – 找到连续整数序列的数量,使得它们的和为零所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。