等值首尾和

文章目錄

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

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));
    }
}