c++ - 有没有更好的方法来实现 2-SUM 算法？

Question

目前，我正在尝试创建一个 2-SUM 算法，给定一组大约 100 万个整数，找到目标值的数量 t (-10,000 <= t <= 10,000) 由集合中任意两个值 x,y 的总和构成。

我对 t 的单个值的 2-SUM 没有问题，只需使用哈希表并在表中查找每个哈希条目 x 如果存在另一个条目 t-x 。这将在 O(N) 时间内运行。

但是，现在我必须找到 t 的多个值，从 -10000 到 10000。如果我只使用普通的 for 循环，那么运行时间现在将为 O(N^2) . 我已经尝试过这段代码，它通过所有 t 从 -10000 到 10000 进行暴力破解，但它运行得太慢(~1 小时执行)。

所以，我的问题是，是否有任何提示可以更好地处理 ~20,001 个目标，而无需暴力破解所有 20,001 个值？

这是我用于我的O(N^2) 解决方案的代码:

for(long long t = -10000; t <= 10000; t++)
{
  for(unordered_set<long long>::iterator it=S.begin(); it != S.end(); ++it)
  {
     long long value = *it;
     if((S.find(t-value) != S.end()) & (t-value != value))
     {
        values++;
        //cout << "Found pair target " << t << " " <<   value << " " << t-value << '\n';
        break;
     }
  }
}

Answer 1

更好的方法是使用有序集(如果值是唯一的，或者如果您关心重复项，则使用有序数组/列表)。

然后，您使用以下方法为您的值搜索匹配对:

1. For each Val (-10000, -9999, ...)
2. Let iS be 0
3. Let iE be length - 1
4. While (S[iS] + S[iE]) != Val
   4.1 (S[iS] + S[iE]) > Val : Binary Search in (iS -> iE - 1) for the maximum value, lower or equal to (Val - S[iS]) and set iE to match.
   4.2 (S[iS] + S[iE]) < Val : Binary Search in (iS +1 -> iE) for the minimum value, higher or equal to (Val - S[iE]) and set iS to match.
   4.3 If iS > iE, Val doesn't exist.

这给你 O(n log(n)) 进行排序，O(m n)(m 是 20001 为 -10000 -> 10000) 用于搜索 尽管实际上，搜索的性能会比 O(m n) 好得多。由于 m > log(n)，整个解决方案是 O(m n)。

它可以通过使用匹配值的映射进一步优化，并且在每次迭代中，在找到匹配后，推进 iE 直到 (S[iS] + S[iE]) > maxValue (10000) 并将所有和标记为已找到，然后外循环中的迭代次数较少。