题解 | #数字组合#

一种基于哈希表的解法

与二分的解法相似，把a[i] + b[j]的所有结果放到ab数组里面

不同的是，可以使用哈希表存储从c[i] + d[j]

用m.count(-ab)可以在最好是o(1)的时间复杂度下找到a+b+c+d = 0

但是题目数据好像卡了

哈希表解法最好的时间复杂度是O(n^2), 插入和查找一般是O(1)

在本题里哈希表比排序+二分慢了200ms

下面是ac代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using I128 = __int128;
using PII = pair<int, int>;

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  int n;
  cin >> n;

  int a[n], b[n], c[n], d[n];
  for (int i = 0; i < n; ++i) {
    cin >> a[i] >> b[i] >> c[i] >> d[i];
  }

  vector<int> ab;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      ab.push_back(a[i] + b[j]);
    }
  }

  unordered_map<int, int> m;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      m[c[i] + d[j]]++;
    }
  }

  LL res = 0;
  for (int i : ab) {
    if (m.count(-i)) {
      res += m[-i];
    }
  }

  cout << res;

  return 0;
}