四数之和为零计数 - 解题思路

这段代码使用分治和二分查找的方法高效地计算四个数组中满足a[i]+b[j]+c[k]+d[l]=0的组合数量。

算法思路

1. 预处理阶段：

   • 将四个数组两两分组，计算c和d数组所有元素两两之和，存入sum数组
   • 对sum数组进行排序，为后续二分查找做准备

2. 查询阶段：

   • 遍历a和b数组的所有元素组合，计算目标值tmp = -(a[i]+b[j])
   • 在预处理的sum数组中使用二分查找：
     • 使用lower_bound找到第一个等于tmp的位置
     • 使用upper_bound找到第一个大于tmp的位置
     • 两者之差即为等于tmp的元素个数

3. 结果统计：

   • 累加所有满足条件的组合数量
   • 输出最终结果

关键点

• 将O(n⁴)的暴力解法优化为O(n² log n)的高效算法
• 使用分治思想将四数之和问题转化为两数之和问题
• 利用排序和二分查找快速统计匹配项数量
• 预处理阶段的空间复杂度为O(n²)
• 适用于中等规模的数据(n≈4000时，n²=16,000,000)

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <cmath>
#include <map>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MN = 65005;
const int MAXN = 1000005;
const int INF = 0x3f3f3f3f;
#define IOS ios::sync_with_stdio(false);
 
int a[4005], b[4005], c[4005], d[4005];
int n;
int sum[16000000];
void solve() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			sum[i * n + j] = c[i] + d[j];
		}
	}
	ll res = 0;
	sort(sum, sum + n * n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int tmp = -(a[i] + b[j]);
			res += upper_bound(sum, sum + n * n, tmp) - lower_bound(sum, sum + n * n, tmp);
		}
	}
	printf("%lld\n", res);
}
 
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d %d %d %d", a + i, b + i, c + i, d + i);
	}
	solve();
	return 0;
}