算法-等值首尾和

算法-等值首尾和

虐人心 发布于 2017-06-04 字数 446 浏览 1246 回复 4

一个数组X[], 它有N个元素,每一个都大于0,称X[0] + X[1] + .... + X[i]为前置和,而X[j] + X[j + 1] + .....+ X[N - 1]为后置和,写程序求X[]有多少组相同的前置和与后置和。
例如X[] = {3, 6, 2, 1, 4, 5, 2}
前置和有以下: 3, 9, 11, 12, 16, 21, 23
后置和有以下: 2, 7, 11, 12, 14, 20, 23
于是11,12,23就是值相同的前置和与后置和。
建议不要使用把所有前置和与后置和都算出来在进行比较的方法,因为这样浪费内存而且效率不高

如果你对这篇文章有疑问,欢迎到本站 社区 发帖提问或使用手Q扫描下方二维码加群参与讨论,获取更多帮助。

扫码加入群聊

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(4

清晨说ぺ晚安 2017-10-04 4 楼

用php写了一个实现你上面的功能:

<?php
function head_tail_sum($arr)
{
$sumArr = array();
if(empty($arr))
{
return $sumArr;
}
$n = count($arr);
$head = $arr[0];
$tail = $arr[$n-1];
$i = 1;
$j = $n-2;
while($i <= $n-1 && $j >= 0)
{
if($head < $tail)
$head += $arr[$i++];
else if($head > $tail)
$tail += $arr[$j--];
else
{
$sumArr[] = $head;
$head += $arr[$i++];
$tail += $arr[$j--];
}
}
return $sumArr;
}
$arr = array('3','6', '2', '1', '4', '5', '2');
$a = head_tail_sum($arr);
print_r($a);
?>

偏爱自由 2017-09-17 3 楼

补一个C语言版的

void headTail(unsigned int *a, int len)
{
unsigned int prefixSum = a[0];
unsigned int suffixSum = a[len - 1];
int preInc = 0;
int sufInc = 0;
int count = 0;

for(preInc = 0, sufInc = len - 1; (preInc < len) && (sufInc >= 0); )
{
if(prefixSum > suffixSum)
{
--sufInc;
suffixSum += a[sufInc];
}
else if(prefixSum < suffixSum)
{
++preInc;
prefixSum += a[preInc];
}
else
{
++count;
printf("prefixSum == suffixSum %dn", prefixSum);
if((preInc == len - 1) || (sufInc == 0))
{
break;
}
else
{
prefixSum += a[++preInc];
suffixSum += a[--sufInc];
}
}
}

printf("count = %dn", count);
}

浮生未歇 2017-07-21 2 楼

import java.util.*;
/**
* @author Administrator 这题我想用2进制的办法比较好,例如3+6的和可用 1100000表示
*/
public class Test2 {
public static void main(String args[]) {
int[] x = { 3, 6, 2, 1, 4, 5, 2 };
int s = 0;// 用来表示2进制数化为10进制的变量
System.out.print("前置和: ");
for (int i = x.length - 1; i >= (-x.length); i--)// 前置
{
if (i >= 0)
s = s + (int) Math.pow(2, i);
else if (i == -1) {
System.out.print("n后置和: ");
s = 1;
} else {
s = s + (int) Math.pow(2, (int) Math.abs(i + 1));
}
int h = s, j = x.length - 1, sum = 0;// 计算二进制数的临时变量,求出的和
for(;j>=0;j--) {
if (h % 2 == 1)
sum += x[j];
h /= 2;
}
System.out.print(sum + " ");
}
}
}

浮生未歇 2017-06-13 1 楼

 /**
* clone a java code
*/
static void returnCount(){
int sourceArray[] = new int[]{3, 6, 2, 1, 4, 5, 2};
int cloneArray[] = new int[sourceArray.length];
System.arraycopy(sourceArray, 0, cloneArray, 0, sourceArray.length);

int count = 0;
int head = 0;
int tail = cloneArray.length -1;

for (;(head < sourceArray.length) && (tail >= 0);) {
if (sourceArray[head] > cloneArray[tail]){
tail--;
cloneArray[tail] += cloneArray[tail+1];
} else if(sourceArray[head] <cloneArray [tail]) {
head++;
sourceArray[head] += sourceArray[head-1];
} else {
System.out.println(sourceArray[head]+","+cloneArray[tail]);
count++;
head++;
tail--;
if (tail >=0) {
cloneArray[tail] += cloneArray[tail+1];
}
if (head<sourceArray.length){
sourceArray[head] += sourceArray[head-1];
}
}
}
System.out.println("total:" + count);
}