LeetCode 的 4 sum 问题如何用hash table做呢？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

LeetCode 的 4 sum 问题如何用hash table做呢？

LeetCode 的 4 sum 问题如何用hash table做呢？# JobHunting - 待字闺中

H*l2013-08-23 07:08

1 楼

我用类似3 sum的方法，是O（n^3)的复杂度，但是过不了large judge，超时；
看到帖子说可以用hash table做到O（n^2）的复杂度，能不能具体说下算法？
题目如下：
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)

f*n2013-08-23 07:08

2 楼

O(n^2)两两配对求和，对这些和再做two sum吧

H*l2013-08-23 07:08

3 楼

怎么在O(n^2)时间内既求和又能对结果排序，还可以从求和后的idx恢复原来两个数的
idx呢……？

【在 f****n 的大作中提到】

: O(n^2)两两配对求和，对这些和再做two sum吧

d*y2013-08-23 07:08

4 楼

基本上2,3,4-sum都是一个思路吧，用hashmao做一个的索引。我之前做
的时候都是优化一个指数级别就可以过large set了。
import java.util.*;
public class Solution {
public ArrayList> fourSum(int[] num, int target) {
// Start typing your Java solution below
// DO NOT write main() function
HashSet> result = new HashSet>
();
HashMap map = new HashMap();
ArrayList> rtn = new ArrayList
>();
Arrays.sort(num);
for (int i = 0; i < num.length; i++) {
map.put(num[i], i);
}
for (int i = 0; i < num.length - 3; i++) {
for (int j = i + 1; j < num.length - 2; j++) {
for (int k = j + 1; k < num.length - 1; k++) {
int diff = target - num[i] - num[j] - num[k];
if (map.containsKey(diff)) {
int l = map.get(diff);
if (l != i && l != j && l != k && l > k) {
ArrayList current = new ArrayList<
Integer>(4);
current.add(num[i]);
current.add(num[j]);
current.add(num[k]);
current.add(num[l]);
result.add(current);
}
}
}
}
}
Iterator> it = result.iterator();
while (it.hasNext()) {
rtn.add(it.next());
}
return rtn;
}
}