登录
  • #刷题
  • #leetcode

关于4 Sum O(n^2logn)解法的问题

eaglesky1990
11881
14
Leetcode中4sum的题目是这样的:

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)

The solution set must not contain duplicate quadruplets.

For example, given array S = {1 0 -1 0 -2 2}, and 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中重复和的问题。比如这篇文章的讨论:tech-wonderland.net 该文中Hash解法复杂度个人觉得并没有快于O(n^3)。

还有这里的解法:geeksforgeeks.org

以及这里的解法: stackoverflow.com

算法思路都是把所有pair的和以及相应两数的index存起来,将四数求和的问题转为二数求和。接下来一种思路是先将存起来的数排序(O(n^2 log n^2), 然后夹逼。注意夹逼时针对的数组中的每个元素实际上是两数和, 会有很多组合,所以如果夹逼时两元素和 == target, 还需要检查每个元素重复值所对应的两个数,这样一来因为一共有O(n^2)个元素,很有可能时间复杂度是O(n^4)。

另外一种思路是所有的pair和存到hashtable中。不过因为一个和可能对应多种组合,个人觉得应该用hash-multimap。这个具体代码在Leetcode题解(C++)版中给出了。 这个multimap里key是两数和,value是两数index,可能有多个,所以比较时也应该所有value对应的元素相互都比较才行,总复杂度感觉也不会是O(n^2)。

不知大家做过此题的人想法怎样。我说的可能不清楚,但很希望能和大家讨论一下此题。

谢谢!
14条回复
热度排序

发表回复