Leetcode:四和

问题描述 投票:2回答:3

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

注意:四元组(a,b,c,d)中的元素必须以降序排列。 (即a≤b≤c≤d)解决方案集不得包含重复的四元组。

例如,给定数组S = {1 0 -1 0 -2 2},并且目标= 0。

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

我知道有一个O(n ^ 3)解决方案,但是我想知道是否有更快的算法。我在Google上搜索了很多东西,发现很多人给出了O(n ^ 2logn)解决方案,当S中存在对和的重复项时,该解决方案无法正确处理(例如herehere)。我希望有人可以给我O(n ^ 2logn)算法的正确版本(如果确实存在)。

谢谢!

arrays algorithm sum
3个回答
2
投票

蛮力算法需要时间O(n ^ 4):使用四个嵌套循环从输入中形成四个项目的所有组合,并将所有和保持在目标位置。

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

我所知道的最好的算法是meet-in-the-middle算法,它在时间O(n ^ 2)中运行:使用两个嵌套循环从输入中形成两项的所有组合,存储对并以总计为索引的某种字典(哈希表,平衡树)中的总计。然后再使用两个嵌套循环,再次形成输入中两个项目的所有组合,并保留嵌套循环中的两个项目以及字典中的两个项目,以求任何对总和为负的项目对字典。

我在my blog处有代码。


0
投票

恕我直言,对于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数组后,可以将其插入到文章中提到的代码中,结果将是正确的。

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


0
投票

这是geeksforgeeks解决方案的修改版本,它也可以处理对和的重复项。我注意到有些对丢失了,因为当哈希表发现新的对满足总和时,哈希表将覆盖旧的对。因此,解决方法是通过将它们存储在成对的向量中来避免覆盖。希望这会有所帮助!

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;    
}
© www.soinside.com 2019 - 2024. All rights reserved.