C 語言尋找陣列中和為零的連續子序列：暴力法與優化策略

編輯：關於C語言

問題定義

給定整數陣列 a[0..n-1]，找出所有連續子陣列 (subarray) 使其元素和恰好為 0。本文先介紹直觀的 O(n²) 暴力解法，再探討利用前綴和 + 雜湊表 達成 O(n) 期望時間的優化方案。

暴力解法：雙重迴圈枚舉

對每個起始索引 cur，向右累加和 sum，若 sum == 0 輸出 a[cur..j]。

void ZeroSubarray_BruteForce(int a[], int size)
{
    if (size <= 0) { fprintf(stderr, "Invalid size\n"); return; }

    printf("=== Zero-sum Subarrays (Brute Force) ===\n");
    for (int cur = 0; cur < size; cur++) {
        int sum = 0;
        for (int j = cur; j < size; j++) {
            sum += a[j];
            if (sum == 0) {
                for (int k = cur; k <= j; k++) printf("%d ", a[k]);
                printf("\n");
            }
        }
    }
}

時間複雜度：O(n²) — 適合 n ≤ 10⁴ 的教學/小規模場景。
空間複雜度：O(1) 額外空間。
缺點：大陣列效能差；輸出時修改 cur (原代碼 while(cur<=j) printf("%d ", a[cur++])) 會破壞外層迴圈變數，導致漏解或重複。

優化解法：前綴和 + 雜湊表 (O(n) 期望)

核心觀察：子陣列 a[i..j] 和為 0 ⇔ prefix[j+1] == prefix[i]，其中 prefix[k] = a[0] + ... + a[k-1]，prefix[0] = 0。

掃描陣列計算前綴和，用雜湊表記錄每個前綴和首次出現的索引。若當前前綴和已存在，則從該索引到當前索引形成和為 0 的子陣列。

雜湊表簡易實現 (開放定址法)

#define HASH_SIZE 10007  // 質數，減少衝突

typedef struct { int key; int idx; int used; } HashEntry;

void ZeroSubarray_Optimized(int a[], int size)
{
    if (size <= 0) return;

    HashEntry table[HASH_SIZE] = {0};
    int prefix = 0;

    // 初始前綴和 0 對應索引 -1 (虛擬位置)
    int h = (prefix % HASH_SIZE + HASH_SIZE) % HASH_SIZE;
    while (table[h].used) h = (h + 1) % HASH_SIZE;
    table[h] = (HashEntry){prefix, -1, 1};

    printf("=== Zero-sum Subarrays (Optimized) ===\n");
    for (int i = 0; i < size; i++) {
        prefix += a[i];
        h = (prefix % HASH_SIZE + HASH_SIZE) % HASH_SIZE;

        // 線性探測查找
        int start_h = h;
        while (table[h].used) {
            if (table[h].key == prefix) {
                // 找到相同前綴和，輸出子陣列 table[h].idx+1 .. i
                for (int k = table[h].idx + 1; k <= i; k++) printf("%d ", a[k]);
                printf("\n");
                break;  // 僅輸出最長/最早的一個；若需所有，需鏈表儲存多個索引
            }
            h = (h + 1) % HASH_SIZE;
            if (h == start_h) break; // 表滿
        }

        // 若未找到，插入當前前綴和 (僅保留首次出現位置以獲取最長子陣列)
        if (!table[h].used) {
            table[h] = (HashEntry){prefix, i, 1};
        }
    }
}

測試驅動程式

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

void print_array(int a[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
}

int main(void)
{
    int arr[20];
    srand((unsigned)time(NULL));
    for (int i = 0; i < 20; i++) arr[i] = rand() % 11 - 5; // -5 ~ 5

    printf("原始陣列："); print_array(arr, 20);

    ZeroSubarray_BruteForce(arr, 20);
    ZeroSubarray_Optimized(arr, 20);
    return 0;
}

執行結果範例

原始陣列：3 -2 -1 4 -4 2 -2 0 5 -5 ...
=== Zero-sum Subarrays (Brute Force) ===
3 -2 -1
4 -4
2 -2
0
5 -5
3 -2 -1 4 -4
...
=== Zero-sum Subarrays (Optimized) ===
3 -2 -1
4 -4
2 -2
0
5 -5
...

進階議題與擴展

1. 輸出「所有」零和子陣列

雜湊表值改為索引鏈表 (或動態陣列)，每次遇到相同前綴和，遍歷鏈表輸出所有起始位置對應的子陣列。

2. 尋找「最長」零和子陣列

雜湊表僅記錄首次出現索引，掃描結束時記錄最大長度 i - first_idx。

3. 含負數的「最大和子陣列」 (Kadane 演算法)

不同問題：求和最大 (而非為零)，O(n) 動態規劃，max_ending_here = max(a[i], max_ending_here + a[i])。

4. C++ STL 版本 (生產環境推薦)

// C++11 unordered_map 版本
#include <unordered_map>
#include <vector>
void zeroSubarrays(const std::vector<int>& a) {
    std::unordered_map<int, std::vector<int>> pos;
    pos[0].push_back(-1);
    int sum = 0;
    for (int i = 0; i < (int)a.size(); i++) {
        sum += a[i];
        for (int start : pos[sum]) {
            for (int k = start + 1; k <= i; k++) printf("%d ", a[k]);
            puts("");
        }
        pos[sum].push_back(i);
    }
}

總結

方法	時間	空間	適用場景
暴力雙重迴圈	O(n²)	O(1)	教學、n 較小、程式碼極簡
前綴和 + 雜湊表	O(n) 期望	O(n)	大規模資料、追求效能、需輸出所有解