C 語言排序與二分查找實戰：三數組求和查詢（優化至 O(L·N·log M)）

問題描述

給三個數組 A[L], B[N], C[M] (L,N,M ≤ 500) 與 S 個查詢 X (S ≤ 1000)，判斷是否存在 A[i] + B[j] + C[k] = X。

優化策略

• 暴力三重循環 O(L·N·M) = 1.25e8，配合 1000 查詢不可行
• 將 C 排序，枚舉 A[i] + B[j]（O(L·N)），對每個和 sum 在 C 中二分查找 X - sum（O(log M)）
• 總複雜度 O(S·L·N·log M) ≈ 1000×500×500×9 ≈ 2.25e9 仍偏大
• 更優：預計算 A[i] + B[j] 所有和存入數組 AB[]（大小 ≤ 250,000），排序 AB，每查詢枚舉 C[k] 二分查找 X - C[k] 在 AB 中 → O(S·M·log(L·N)) ≈ 1000×500×18 ≈ 9e6，極快

完整代碼（優化版）

#include 
#include 

#define MAXL 500
#define MAXN 500
#define MAXM 500
#define MAXAB (MAXL*MAXN)

int A[MAXL], B[MAXN], C[MAXM];
int AB[MAXAB];
int ab_cnt;

int cmp_int(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

int binary_search(int arr[], int n, int target) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (arr[mid] == target) return 1;
        if (arr[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return 0;
}

int main() {
    int L, N, M, S, X, case_no = 1;
    while (scanf("%d %d %d", &L, &N, &M) == 3) {
        for (int i = 0; i < L; i++) scanf("%d", &A[i]);
        for (int i = 0; i < N; i++) scanf("%d", &B[i]);
        for (int i = 0; i < M; i++) scanf("%d", &C[i]);
        scanf("%d", &S);

        /* 預計算 A+B 所有和 */
        ab_cnt = 0;
        for (int i = 0; i < L; i++)
            for (int j = 0; j < N; j++)
                AB[ab_cnt++] = A[i] + B[j];
        qsort(AB, ab_cnt, sizeof(int), cmp_int);

        printf("Case %d:\n", case_no++);
        while (S--) {
            scanf("%d", &X);
            int found = 0;
            for (int k = 0; k < M && !found; k++) {
                int need = X - C[k];
                if (binary_search(AB, ab_cnt, need)) found = 1;
            }
            puts(found ? "YES" : "NO");
        }
    }
    return 0;
}

複雜度對比

關鍵細節

• qsort 比較函數返回 a-b 可能溢出，工程用 (a>b)-(a 或 int64_t 差值
• 輸入可能多組測試用例，while(scanf(...)==3) 正確處理
• 輸出格式 Case d: 逐行 YES/NO