d563: 等值首尾和

內容

假設有一個陣列 x[]，它有 n 個元素，每一個都大於零；我們說 x[0]+x[1]+…+x[i]是個前段和(Prefix Sum)，而 x[j]+x[j+1]+…+x[n-1]則是個後段和(Suffix Sum)。請寫一個程式，求出 x[]中有多少組相同的前段和與後段和。

(上述文字、題目來自名題精選百則 - 冼鏡光著 - 儒林出版)

輸入

每個測資檔只有一組測資，共兩行。
第一行整數 n(1<=n<=100000)代表數列有幾個數字
第二行有 n 個正整數(A1,A2,…,An)，並且全部總合小於 2147483647，以空格隔開

–

範例測資 3,6,2,1,4,5,2 有三組等值首尾和，分別是：

11 = 3+6+2 = 2+5+4

12 = 3+6+2+1 = 2+5+4+1

23 = 3+6+2+1+4+5+2 = 2+5+4+1+2+6+3 (全部陣列的和，也代表答案至少有一組)

7
3 6 2 1 4 5 2

輸出

等值首尾和的數目

3

解題思路

兩指針分別指向陣列頭尾，然後比較累加的值是否相同，若是相同數量加一，反之則將累加較小的指針向另一邊偏移一個元素並加上該元素，如此循環直到某指針脫離陣列，輸出答案即可。

完整程式碼

AC (11ms, 472KB)

#include <stdio.h>

int list[100010];

int main()
{
    int n, sumL, sumR, count = 0;
    scanf(" %d", &n);
    for (int i = 0; i < n; i++)
        scanf(" %d", list + i);
    sumL = list[0], sumR = list[n - 1];
    for (int l = 0, r = n - 1; l < n && ~r;)
    {
        if (sumL > sumR)
            sumR += list[--r];
        else if (sumR > sumL)
            sumL += list[++l];
        else
        {
            sumR += list[--r];
            sumL += list[++l];
            count++;
        }
    }
    printf("%d\n", count);
    return 0;
}