首页 > 代码库 > 等值首尾和问题及其思考、解决和总结

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

2024-07-02 04:14:34   226人阅读

问题 等值首尾和

  假设有一个数组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


联系
我们