等值首尾和问题及其思考、解决和总结

问题 等值首尾和

  假设有一个数组x[]，它有n个元素，每一个都大于零；称x[0] + x[1] + … + x[i]为前置和（Prefix Sum）,

而x[j] + x[j+1] + … + x[n-1]为后置和(Suffix Sum)。试编写一个程序，求出x[]中有多少组相同的前置和与后置和。

 

  最容易想到的当然是把前置和与后置和分别算出来放到两个长度为n的数组里面，再检索两个数组相同的元素。

但我们可以注意到每个元素都大于0，所以前置和与后置和都是递增的。于是我们可以：

设置前后两个游标

   前置和大于后置和，则后游标向前移位，同时后置和加上相应元素；

   同理，前置和小于后置和，前游标向后移位，前置和加上相应元素；

   两者相等，则统计数目加1，同时执行两步操作。

直到某一个或两个游标到达终点

 

下面是我的代码

1 // 最差情况，交替上升,执行代码 2n 次,n为数组长度 2 int GetHeadTail(int * a, int lenA) 3 { 4 int count = 0; // 统计数 5 int prefixSum = 0; // 前置和 6 int suffixSum = 0; // 后置和 7 int head = 0; // 前游标 8 int tail = lenA - 1; // 后游标 9 while (head < lenA && tail >= 0) 10 { 11 prefixSum += a[head++]; 12 suffixSum += a[tail--]; 13 while (prefixSum < suffixSum && head < lenA) 14 { // 向后遍历 15 prefixSum += a[head++]; 16 } 17 while (suffixSum < prefixSum && tail >= 0) 18 { // 向前遍历 19 suffixSum += a[tail--]; 20 } 21 if (prefixSum == suffixSum) 22 { 23 count++; 24 } 25 } 26 return count; 27 }

 

  本来用的for循环，逻辑一样，却导致代码看上去很凌乱。后来改成了while循环，简洁多了。因此还沾沾自喜，再看看作者的答案

1 int head_tail(int x[], int n) 2 { 3 int prefix = 0, suffix = 0; 4 int prefix_idx = 0, suffix_idx = n - 1; 5 int count = 0; 6 7 while (prefix_idx < n && suffix_idx >= 0) 8 { 9 if (prefix < suffix) 10 prefix += x[prefix_idx++]; 11 else if (suffix < prefix) 12 suffix += x[suffix_idx--]; 13 else { 14 count++; 15 suffix += x[suffix_idx--]; 16 prefix += x[prefix_idx++]; 17 } 18 } 19 return count; 20 }

作者的逻辑清晰，代码整洁。  而我的还有一个bug————可能会漏掉前后全部加完的情况。

 

问题及答案来源————《C语言名题精选百则技巧篇》问题1.5

转载于:https://www.cnblogs.com/blogXy/p/3701153.html

相关资源：JAVA上百实例源码以及开源项目