假设有一个数组x[ ],它有n个元素,每一个都大于0;称x[0]+x[1]+...+x[i]为前置和,而x[j]+x[j+1]+...+x[n-1]为后置和。试求出x[ ]中有多少前置和与后置和。
例如,x[7] = {3,6,2,1,4,5,2},于是x[ ]的前置和有以下7个,即3,9,11,12,16,21,23;后置和则是2,7,11,12,14,20,23,于是11、12和23这3对就是值相同的前置和与后置和。建议不要把所有的前置和与后置和都算出来。 解答: 注意前提条件:x[ ]中的元素都大于0。设两个指针变量i、j分别指向数组的前端和后端,并且设置两个变量head、tail,保存当前的前置和与后置和。head与tail的关系有3种情况: (1)head < tail。说明当前的前置和小于后置和,必须往前置和里面添加元素才可能使二者相等。head += x[i++]; (2)head > tail。说明当前的后置和小于前置和,必须往后置和里面添加元素才可能使二者相等。tail += x[j--]; (3)head = tail。得到一组符合要求的数值。此时前置和与后置和都必须继续添加元素。 代码: int head_tail(int x[ ], int n) { int head = x[0], tail = x[n-1]; int i = 1, j = n-2; int count = 0; while(i <= n-1 && j >= 0) { if(head < tail) head += x[i++]; else if(head > tail) tail += x[j--]; else { count ++; head += x[i++]; tail += x[j--]; } } return count; }