Leetcode:四和

Question

问题:给定一个由n个整数组成的数组S，S中是否存在元素a，b，c和d，使得a+b+c+d= target？在数组中找到所有唯一的四元组，它给出了目标的总和。

注意:四元组(a，b，c，d)中的元素必须是非降序的。(即a≤b≤c≤d)解集不能包含重复的四元组。

例如，给定数组S= {1 0 -1 0 -2 2}，且target =0。

A solution set is:
(-1,  0, 0, 1)
(-2, -1, 1, 2)
(-2,  0, 0, 2)

我知道这个问题有一个O(n^3)的解决方案，但我想知道是否有更快的算法。我在谷歌上搜索了很多，发现许多人给出了O(n^2logn)解决方案，当S中存在重复的配对和(如here和here)时，该解决方案无法正确处理。如果O(n^2logn)算法确实存在，我希望有人能给我一个正确的版本。

谢谢!

Answer 1

暴力算法耗时O(n^4)：使用四个嵌套循环来形成来自输入的四个项目的所有组合，并将所有这些项目的总和保留到目标。

一个简单的改进需要O(n^3)时间:使用三个嵌套循环来形成来自输入的三个项的所有组合，并将任何和保持为目标的负数。

我所知道的最好的算法是中间相遇算法，它的运行时间为O(n^2)：使用两个嵌套循环来形成输入中两个项目的所有组合，将配对和合计存储在某种按合计索引的字典(哈希表、平衡树)中。然后，再使用两个嵌套循环来再次形成来自输入的两个项的所有组合，并保留嵌套循环中的两个项以及字典中的两个项，对于字典中总和为负数的任何一对项。

我在my blog上有代码。

Answer 2

对于O(n^2lgn)算法，在创建aux[]数组时，可以解决重复的问题。(我在您提供的第二个链接中使用了该名称)。其基本思想是首先对输入中的元素进行排序，然后在处理数组时跳过重复项。

vector<int> createAuxArray(vector<int> input) {
  int len = input.size();
  vector<int> aux;

  sort(input.begin(), input.end());

  for (int i = 0; i < len; ++i) {
    if (i != 0 && input[i] == input[i - 1]) continue; // skip when encountered a duplicate

    for (int j = i + 1; j < len; ++j) {
      if (j != i + 1 && input[j] == input[j - 1]) continue; // same idea

      aux.push_back(createAuxElement(input[i], input[j]); 
    }
  }
  return aux;
}

这个模块的复杂度是O(nlgn) + O(n^2) = O(n^2)，这不会影响整体性能。一旦我们创建了aux数组，我们可以将它插入到post中提到的代码中，结果将是正确的。

请注意，可以使用BST或哈希表来代替排序，但通常它不会降低复杂性，因为您必须在2嵌套循环中插入/查询(O(lgN))。

Answer 3

这是geeksforgeek解决方案的修改版本，它还可以处理成对求和的副本。我注意到一些对丢失了，因为当哈希表找到满足和的新对时，它会覆盖旧的对。因此，修复方法是通过将它们存储在成对的向量中来避免覆盖。希望这能有所帮助！

vector<vector<int> > fourSum(vector<int> &a, int t) {
    unordered_map<int, vector<pair<int,int> > > twoSum;
    set<vector<int> > ans;
    int n = a.size();
    for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) twoSum[a[i] + a[j]].push_back(make_pair(i, j));
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (twoSum.find(t - a[i] - a[j]) != twoSum.end()) {
                for (auto comp : twoSum[t - a[i] - a[j]]) {
                    if (comp.first != i and comp.first != j and comp.second != i and comp.second != j) {
                        vector<int> row = {a[i], a[j], a[comp.first], a[comp.second]};
                        sort(row.begin(), row.end());
                        ans.insert(row);
                    }
                }
            }
        }
    }
    vector<vector<int> > ret(ans.begin(), ans.end());
    return ret;    
}