C語言實作：尋找陣列中前綴和等於後綴和的配對數（等值首尾和）

陣列前綴和與後綴和匹配

給定陣列 num[]，計算所有前綴和（從左累加）與所有後綴和（從右累加），統計有多少組 (i, j) 使得 prefix_sum[i] == suffix_sum[j]。

問題描述

陣列 {3, 6, 2, 1, 4, 5, 2} (長度 7)。
前綴和：3, 9, 11, 12, 16, 21, 23
後綴和：23, 20, 14, 12, 11, 7, 2
找出相等的配對數。

程式碼實作

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i, j, n, count = 0;
    int prefix[7] = {0}, suffix[7] = {0};
    int num[] = {3, 6, 2, 1, 4, 5, 2};

    n = 0;
    for(i = 0; i < 7; i++) { n += num[i]; prefix[i] = n; }

    n = 0;
    for(i = 6; i >= 0; i--) { n += num[i]; suffix[i] = n; }

    for(i = 0; i < 7; i++)
        for(j = 0; j < 7; j++)
            if(prefix[i] == suffix[j]) count++;

    printf("陣列num[]中有%d組 前置和等於後置和\n", count);
    return 0;
}

手動驗證

共 3 組匹配。程式輸出應為 3。

最佳化：雜湊集合 O(n)

將所有後綴和存入雜湊集合，遍歷前綴和查找是否存在：

// 假設有雜湊集合實作
HashSet set;
for(i = 0; i < 7; i++) set.add(suffix[i]);
for(i = 0; i < 7; i++) if(set.contains(prefix[i])) count++;

時間從 O(n²) 降為 O(n)。

概念延伸

• 若要求 i < j（前綴在後綴左側），則為尋找「平衡點」或「可分割點」。
• LeetCode 724「尋找陣列的中心索引」即為特例：prefix[i-1] == suffix[i+1]。