文章目錄

假设有一个数组x[ ], 它有n个元素,每一个都大于零,称x[0] + x[1] + … + x[i]为前置和(Prefix Sum),而 x[j] + x[j + 1] + … + x[n - 1]为后置和(Suffix Sum)。试编写一个程序,求出x[ ] 中有多少组相同的前置和与后置和。

说明
如果x[ ] 的元素是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对就是值相同的前置和与后置和,因为:
11 = 3 + 6 + 2(前置和) = 2 + 5 + 4 (后置和)
12 = 3 + 6 + 2 + 1(前置和) = 2 + 5 + 4 + 1 (后置和)
因为23是整个数组元素的和,因此前置和与后置和一定相同。

可以用变量prefix来表示前置和,用suffix来表示后置和,用i表示前置和累加元素的位置,i从前往后加,用j表示后置和累加元素的位置, j从后往前加。当prefix > suffix时,累加后置和,也就是j向前走;当prefix < suffix时,累加前置和,也就是i往后走;当prefix == suffix时,同时累加前置和与后置和,也就是i往后走,j往前走

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class HeadTail {
public static int headTail(int[] nums) {
int i = 0;
int j = nums.length - 1;
int prefix = 0;
int suffix = 0;
int result = 0;
while (i < nums.length && j >= 0) {
System.out.println(prefix + " " + suffix + " " + i + " " + j);
if (prefix == suffix) {
prefix += nums[i++];
suffix += nums[j--];
result++;
} else if (prefix > suffix) {
suffix += nums[j--];
} else {
prefix += nums[i++];
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {3, 6, 2, 1, 4, 5, 2};
System.out.println(headTail(nums));
}
}
文章目錄