C語言實現：查找數組中和為零的所有子序列

問題描述

給定一個整數數組，找出所有連續子序列，使其元素之和等於零。本文採用隨機生成測試數據，雙重循環窗口法求解。

核心算法實現

隨機數據生成

int arr[10];
void randData(int a[], int start, int end) {
    srand(time(NULL));
    for (int i = start; i <= end; ++i)
        a[i] = rand() % 10 - 5;  // 生成[-5, 4]範圍隨機數
    
    printf("生成新的序列 :");
    print(a, start, end);
    printf("\n");
}

零和子序列查找

void ZeroSubarray(int a[], int size) {
    if (size <= 0) {
        perror("error array size");
        return;
    }
    
    printf("************\n");
    for (int cur = 0; cur < size; cur++) {
        int sum = 0;
        for (int j = cur; j < size; j++) {
            sum += a[j];
            if (sum == 0) {
                // 輸出從cur到j的子序列
                while (cur <= j) {
                    printf("%d ", a[cur++]);
                }
                printf("\n************\n");
            }
        }
    }
}

算法複雜度分析

• 時間複雜度：O(n²) - 雙重循環遍歷所有可能子序列
• 空間複雜度：O(1) - 僅使用常數額外空間
• 優化方向：可用前綴和+哈希表優化至O(n)，但無法直接輸出所有子序列

運行示例

工程應用建議

對於大規模數據，建議採用前綴和+哈希表記錄首次出現位置，可在O(n)時間內判斷是否存在零和子序列。若需輸出所有解，雙重循環仍是直觀可靠的選擇，注意處理整數溢出風險。