算法-等值首尾和

WP主题Bug提交 WP主题Bug提交 主题:1067 回复:2226

算法-等值首尾和

虐人心 发布于 2017-06-04 字数 446 浏览 1208 回复 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就是值相同的前置和与后置和。
建议不要使用把所有前置和与后置和都算出来在进行比较的方法,因为这样浪费内存而且效率不高

发布评论

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

支持 Markdown 语法,需要帮助?

评论(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 &lt; len) &amp;&amp; (sufInc &gt;= 0); )
{
    if(prefixSum &gt; suffixSum)
    {
        --sufInc;
        suffixSum += a[sufInc];
    }
    else if(prefixSum &lt; 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);
    }