UVA 1152：4 Values whose Sum is 0 - 四數組和為零 (雙指針/二分)

問題描述

給定四個長度 n ≤ 4000 的數組 A, B, C, D，求四元組 (a,b,c,d) 使 a+b+c+d=0 的個數。直接 O(n^4) 超時。

Meet-in-the-Middle (二分查找)

1. 計算所有 A[i] + B[j] 存入數組 AB，大小 n^2。
2. 排序 AB。
3. 枚舉所有 C[k] + D[l]，在 AB 中二分查找 -(C[k]+D[l]) 的出現次數（upper_bound - lower_bound）。
4. 累加計數。

代碼實現

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 4005;
int A[MAXN], B[MAXN], C[MAXN], D[MAXN];
int AB[MAXN * MAXN];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        for (int i = 0; i < n; ++i) scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]);
        int m = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                AB[m++] = A[i] + B[j];
        sort(AB, AB + m);
        long long ans = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j) {
                int target = -C[i] - D[j];
                ans += upper_bound(AB, AB+m, target) - lower_bound(AB, AB+m, target);
            }
        printf("%lld\n", ans);
        if (T) puts(""); // 題目要求案例間空行
    }
    return 0;
}

複雜度

• 生成 AB：O(n^2)。
• 排序 AB：O(n^2 log n)。
• 枚舉 CD 查找：O(n^2 log n)。
• 總體 O(n^2 log n)，n=4000 時 n^2=1.6e7，排序與查找在時限內可行。

優化技巧

• 用 static 數組避免重複分配。
• 宏定義 lower_bound/upper_bound 簡化代碼。
• 答案用 long long 存儲，最大可能 n^4 = 2.56e14。

總結

經典「四數組和為零」問題，Meet-in-the-Middle 將 O(n^4) 降至 O(n^2 log n)。同類問題：4Sum (LeetCode 18)、兩數組和查找 等。