Judge：https://vjudge.net/problem/UVA-1152 题意：给定4个n元素集合A，B，C，D，要求分别从中选取一个元素a，b，c，d，使得四个数之和为零。求一共有多少种选法。
n的最大值为4000，时间限制为9000ms。
很明显四重循环枚举是肯定会超时。这里采用中途相遇法，枚举所有a+b并保存起来，然后再枚举-c-d与刚才的a+b对照。
对照的方法有很多种，可以使用二分查找或哈希表。
使用二分查找：（2910ms）
#include <iostream> #include <cstring> #include <algorithm> using namespace std; long long g_arrNum[4][4010]; long long g_arrSum[4000 * 4000 + 10], g_iTop = -1; int main() { int iDataTot; cin >> iDataTot; while (iDataTot--) { memset(g_arrNum, 0, sizeof(g_arrNum)); int iNumTot, iResult = 0, g_iTop = -1; cin >> iNumTot; for (int i = 1; i <= iNumTot; i++) for (int j = 1; j <= 4; j++) cin >> g_arrNum[j - 1][i]; for (int i = 1; i <= iNumTot; i++) for (int j = 1; j <= iNumTot; j++) g_arrSum[++g_iTop] = (g_arrNum[0][i] + g_arrNum[1][j]); sort(g_arrSum, g_arrSum + g_iTop + 1); for (int i = 1; i <= iNumTot; i++) for (int j = 1; j <= iNumTot; j++) iResult += upper_bound(g_arrSum, g_arrSum + g_iTop + 1, -(g_arrNum[2][i] + g_arrNum[3][j])) - lower_bound(g_arrSum, g_arrSum + g_iTop + 1, -(g_arrNum[2][i] + g_arrNum[3][j])); cout << iResult << endl; if (iDataTot) cout << endl; } return 0; }使用哈希表：（采用链表实现）（2300ms）
#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define HASH_MAX 23456789 struct SHashNode { long iData; int iTime; SHashNode * pNext; }; int g_arrNum[4][4010]; SHashNode g_arrHash[HASH_MAX]; void InsertHash(long iData) { int i = (iData >= 0 ? iData % HASH_MAX : iData % HASH_MAX + HASH_MAX); SHashNode * pNode = &g_arrHash[i]; while (pNode->pNext) { if (pNode->pNext->iData == iData) { pNode->pNext->iTime++; return; } pNode = pNode->pNext; } pNode->pNext = new SHashNode; pNode->pNext->iTime = 1; pNode->pNext->iData = iData; pNode->pNext->pNext = 0; } int FindHash(long iData) { int i = (iData >= 0 ? iData % HASH_MAX : iData % HASH_MAX + HASH_MAX); SHashNode * pNode = &g_arrHash[i]; while (pNode->pNext) { if (pNode->pNext->iData == iData) return pNode->pNext->iTime; pNode = pNode->pNext; } return 0; } int main() { int iDataTot; cin >> iDataTot; while (iDataTot--) { memset(g_arrNum, 0, sizeof(g_arrNum)); memset(g_arrHash, 0, sizeof(g_arrHash)); int iNumTot, iResult = 0; cin >> iNumTot; for (int i = 1; i <= iNumTot; i++) for (int j = 1; j <= 4; j++) cin >> g_arrNum[j - 1][i]; for (int i = 1; i <= iNumTot; i++) for (int j = 1; j <= iNumTot; j++) InsertHash(g_arrNum[0][i] + g_arrNum[1][j]); for (int i = 1; i <= iNumTot; i++) for (int j = 1; j <= iNumTot; j++) iResult += FindHash(-(g_arrNum[2][i] + g_arrNum[3][j])); cout << iResult << endl; if (iDataTot) cout << endl; } return 0; }在本题目使用vector实现哈希表也是可以的，但时间略长，不过也长不了多少。