脚本宝典收集整理的这篇文章主要介绍了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)效率?
sum[i] = arr[0] + arr[1] + ... + arr[i]
并且,另外一个开头的单个条目为0(处理从开头开始并总和为零的子数组)
现在,很容易看出,对于每两个索引i,j使得i
注意,如果例如在数组和中有数字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,请注明来意。