求个4sum的算法 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

求个4sum的算法

求个4sum的算法# JobHunting - 待字闺中

c*p2013-08-07 07:08

1 楼

leetcode变聪明了吧？
我的4sum明明可以过大oj的，怎么现在过不了了？
谁有好点的版本？
我的版本是：
把两两的和，放到hashtable里，有重复数字，也重复一遍，hashtable里的值是int[2]
, 每个值表示index而不是值。key是sum。
两两的sum在int[] sum中再存一遍。然后sort。里边有重复的。
return的结果放到hashset里，避免重复。
然后把两两sum过一遍，遇到target - sum[i]在hashtable里存在的，把hashset里的这
2个key对应int[]都就试一次，去看每一组index是否有重复，没有，就排列好，塞
return的hashset里。
以前可以的，现在只能过小oj了。。。桑心。。。
求高人指教。

l*y2013-08-07 07:08

2 楼

照着2sum写。o(n^3)

c*p2013-08-07 07:08

3 楼

过不去了，我写的就是这个。。。
你去试试你以前写的版本，看能不能过。。。
我试了2个版本，加上我新写的，都过不去了。。。

【在 l********y 的大作中提到】

: 照着2sum写。o(n^3)

s*n2013-08-07 07:08

4 楼

羡慕呀，楼上都刷第二遍了

z*e2013-08-07 07:08

5 楼

leetcode 不超过两秒就可以过大oj
我用了800毫秒，还有1200毫秒富余
把你的code贴上来看看
Run Status: Accepted!
Program Runtime: 864 milli secs
public class Solution {
public ArrayList> fourSum(int[] num, int target) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList> list = new ArrayList>>();
Set set = new HashSet>();
Arrays.sort(num);
for(int i=0;ifor(int j=i+1;jint k=j+1,l=num.length-1;
while(kif(num[i]+num[j]+num[k]+num[l]==target){
ArrayList result = new ArrayList();
result.add(num[i]);
result.add(num[j]);
result.add(num[k]);
result.add(num[l]);
set.add(result);
k++;
l--;
while(kwhile(l>k&&l==l+1) l--;
}else if(num[i]+num[j]+num[k]+num[l]>target){
l--;
}else{
k++;
}
}
}
}
list.addAll(set);
return list;
}
}

z*e2013-08-07 07:08

6 楼

java要弄清楚hashtable和hashmap的区别
这是基础题，leetcode显然是用hashmap合适
hashset会自动删除重复数据，不需要你去check
直接压进去就行了

g*42013-08-07 07:08

7 楼

我的大小都能过，就是按照3sum写的

【在 c********p 的大作中提到】

: 过不去了，我写的就是这个。。。
: 你去试试你以前写的版本，看能不能过。。。
: 我试了2个版本，加上我新写的，都过不去了。。。

c*p2013-08-07 07:08

8 楼

你发来看看嘛。

【在 g**4 的大作中提到】

: 我的大小都能过，就是按照3sum写的

c*p2013-08-07 07:08

9 楼

这个是以前写的。。这个当时是可以过大oj的。
和我这次写的，意思是一样的。。。
我就是按照以前能过的写的。。。结果都过不了了
import java.util.*;
public class Solution {
public ArrayList> fourSum(int[] num, int target) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList> result = new ArrayListInteger>>();
HashSet> set = new HashSet>();

if(num == null || num.length < 4){
return result;
}
Arrays.sort(num);
Hashtable> tab = new HashtableArrayList>();
int len = num.length * (num.length - 1) / 2;
int[] sumTwo = new int[len];
int id = 0;
for(int i = 0; i < num.length; i++){
for(int j = i + 1; j < num.length; j++){
int sum = num[i] + num[j];
sumTwo[id] = sum;
id++;
int[] arr = new int[2];
arr[0] = i;
arr[1] = j;
if(tab.containsKey(sum)){
ArrayList temp = tab.get(sum);
temp.add(arr);
}else{
ArrayList temp = new ArrayList();
temp.add(arr);
tab.put(sum, temp);
}
}
}

Arrays.sort(sumTwo);
for(int i = 0; i < sumTwo.length; i++){
int remind = target - sumTwo[i];
if(tab.containsKey(remind)){
ArrayList firstTwo = tab.get(sumTwo[i]);
ArrayList lastTwo = tab.get(remind);

for(int k = 0; k < firstTwo.size(); k++){
for(int l = 0; l < lastTwo.size(); l++){
int[] fTwo = firstTwo.get(k);
int[] lTwo = lastTwo.get(l);
if(fTwo[0] != lTwo[0] && fTwo[0] != lTwo[1] && fTwo[1
] != lTwo[0] && fTwo[1] != lTwo[1]){
ArrayList comb = new ArrayList();
comb.add(num[fTwo[0］);
comb.add(num[fTwo[1］);
comb.add(num[lTwo[0］);
comb.add(num[lTwo[1］);
Collections.sort(comb);
set.add(comb);
}
}
}
}
}
if(!set.isEmpty()){
return new ArrayList>(set);
}
return result;
}
}

Integer

【在 z****e 的大作中提到】

: leetcode 不超过两秒就可以过大oj
: 我用了800毫秒，还有1200毫秒富余
: 把你的code贴上来看看
: Run Status: Accepted!
: Program Runtime: 864 milli secs
: public class Solution {
: public ArrayList> fourSum(int[] num, int target) {
: // Start typing your Java solution below
: // DO NOT write main() function
: ArrayList> list = new ArrayList

c*p2013-08-07 07:08

10 楼

去试试你的，我用你的也过不了。。。
难道是我的问题？
rp不行？

【在 z****e 的大作中提到】

: java要弄清楚hashtable和hashmap的区别
: 这是基础题，leetcode显然是用hashmap合适
: hashset会自动删除重复数据，不需要你去check
: 直接压进去就行了

z*e2013-08-07 07:08

11 楼

那就多刷几次
应该是jvm在你测试的过程中启动了一下gc
导致时间超时
leetcode现在刷的人太多了
内存不够用了

【在 c********p 的大作中提到】

: 去试试你的，我用你的也过不了。。。
: 难道是我的问题？
: rp不行？

c*p2013-08-07 07:08

12 楼

你的，我刷了3次，就一次过了。。。。囧。。。
另外你程序里有个地方写错了，但不影响结果。因为用了hashset。
while后边的 k == k+1, 这个不对吧。。。还有下边那个l == l+1

【在 z****e 的大作中提到】

: 那就多刷几次
: 应该是jvm在你测试的过程中启动了一下gc
: 导致时间超时
: leetcode现在刷的人太多了
: 内存不够用了

c*p2013-08-07 07:08

13 楼

我发错版本了。。。

c*p2013-08-07 07:08

14 楼

这个是今天的。。。
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> set = new HashSet>();

if(num == null || num.length <= 3){
return new ArrayList>(set);
}

Arrays.sort(num);
Hashtable> hash = new HashtableArrayList>();
int twoSumPair = num.length * (num.length - 1)/2;
int[] two = new int[twoSumPair];
int id = 0;
for(int i = 0; i < num.length; i++){
for(int j = i + 1; j < num.length; j++){
int sum = num[i] + num[j];
int[] arr = {i,j};
two[id] = sum;
id++;
if(hash.containsKey(sum)){
ArrayList list = hash.get(sum);
list.add(arr);
hash.put(sum, list);
}else{
ArrayList list = new ArrayList();
list.add(arr);
hash.put(sum, list);
}
}
}

Arrays.sort(two);
for(int i = 0; i < two.length; i++){
System.out.print( " " + two[i] + " ");
}
for(int i = 0; i < two.length; i++){
if(i != 0 && two[i] == two[i - 1]){
continue;
}
int left = target - two[i];
// System.out.println
if(hash.containsKey(left)){
ArrayList firstTwo = hash.get(two[i]);
ArrayList lastTwo = hash.get(left);
for(int m = 0; m < firstTwo.size(); m++){
for(int n = 0; n < lastTwo.size(); n++){
int[] array = new int[4];
int a = firstTwo.get(m)[0];
int b = firstTwo.get(m)[1];
int c = lastTwo.get(n)[0];
int d = lastTwo.get(n)[1];
// System.out.println("a " + a + "b " + b + "c" + c + "d"
+ d);
if(a == c || a == d || b == c || b == d){
continue;
}
array[0] = num[a];
array[1] = num[b];
array[2] = num[c];
array[3] = num[d];
Arrays.sort(array);
ArrayList four = new ArrayList();
for(int ct = 0; ct < 4; ct++){
four.add(array[ct]);
}
set.add(four);
}
}
hash.remove(left);
}
hash.remove(two[i]);
}
return new ArrayList>(set);
}
}

【在 z****e 的大作中提到】

: 那就多刷几次
: 应该是jvm在你测试的过程中启动了一下gc
: 导致时间超时
: leetcode现在刷的人太多了
: 内存不够用了

z*e2013-08-07 07:08

15 楼

那两行删掉就是了，之前写3sum时候留下的

【在 c********p 的大作中提到】

: 你的，我刷了3次，就一次过了。。。。囧。。。
: 另外你程序里有个地方写错了，但不影响结果。因为用了hashset。
: while后边的 k == k+1, 这个不对吧。。。还有下边那个l == l+1

z*e2013-08-07 07:08

16 楼

怎么还有system.out.
那两行如果你想写上去的话，那就是，会快一点点
while(k while(l>k&&num[l]==num[l+1]) l--;

【在 c********p 的大作中提到】

: 这个是今天的。。。
: 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> set = new HashSet>();
:
: if(num == null || num.length <= 3){
: return new ArrayList>(set);

g*42013-08-07 07:08

17 楼

196ms，C++果然是快啊
class Solution {
public:
vector > fourSum(vector &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > result;
if (num.size() < 4) {
return result;
}
sort(num.begin(),num.end());
for (int j=0;jint a = num[j];
// 3sum
for (int i=j+1;iint b = num[i];
int left = i+1;
int right = num.size() - 1;
// 2sum
while (left < right) {
int c = num[left];
int d = num[right];
int sum = a + b + c + d;
if (sum == target) {
vector t = {a,b,c,d};
if (find(result.begin(), result.end(), t) == result.
end()) {
result.push_back(t);
}
right--;
left++;
}else if (sum < target) {
left++;
}else {
right--;
}
}
}

}
}
};

【在 c********p 的大作中提到】

: 你发来看看嘛。

c*p2013-08-07 07:08

18 楼

哦，那个是我测试用的。。。。

【在 z****e 的大作中提到】

: 怎么还有system.out.
: 那两行如果你想写上去的话，那就是，会快一点点
: while(k: while(l>k&&num[l]==num[l+1]) l--;

c*p2013-08-07 07:08

19 楼

哭了，c+＋可以飘过了。
我用java写。经常把c++代码直接翻译过来发现过不了大oj。

【在 g**4 的大作中提到】

: 196ms，C++果然是快啊
: class Solution {
: public:
: vector > fourSum(vector &num, int target) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: vector > result;
: if (num.size() < 4) {
: return result;
: }

z*e2013-08-07 07:08

20 楼

java就是把简单的变复杂，把复杂的变简单
写hello world的话，java是最麻烦的

【在 c********p 的大作中提到】

: 哭了，c+＋可以飘过了。
: 我用java写。经常把c++代码直接翻译过来发现过不了大oj。

c*p2013-08-07 07:08

21 楼

快看看我的复杂度是多少。。。
是o(n(^2)么？

【在 z****e 的大作中提到】

: java就是把简单的变复杂，把复杂的变简单
: 写hello world的话，java是最麻烦的

z*e2013-08-07 07:08

22 楼

不止吧，我依稀看到了三重循环在里面

【在 c********p 的大作中提到】

: 快看看我的复杂度是多少。。。
: 是o(n(^2)么？

c*p2013-08-07 07:08

23 楼

是哦，同样是3层，还是你的方法简洁。。。

【在 z****e 的大作中提到】

: 不止吧，我依稀看到了三重循环在里面

l*02013-08-07 07:08

24 楼

A solution that could deal with dups. O(N^3).
public ArrayList> fourSum(int[] num, int target) {
int len=num.length;
Arrays.sort(num);
ArrayList> results=new ArrayListInteger>>();
for(int i=0;iif(i-1>=0&&num[i]==num[i-1]) continue; //skip dup in outmost
loop
for(int j=i+1;jif(j-1>=i+1&&num[j]==num[j-1]) continue; //skip dup in 2nd
outmost loop

int left=j+1;
int right=len-1;

while(leftint sum=num[i]+num[j]+num[left]+num[right];
if(sum==target){
ArrayList list=new ArrayList();
list.add(num[i]);
list.add(num[j]);
list.add(num[left]);
list.add(num[right]);
results.add(list);

left++;
right--;
while(leftleft-1]) left++; //skip dup
while(leftright]) right--; //skip dup
}else if(sumleft++;
}else{
right--;
}

}
}
}
return results;
}

f*p2013-08-07 07:08

25 楼

笨死！你还是进尼姑庵吧～

【在 c********p 的大作中提到】

: 过不去了，我写的就是这个。。。
: 你去试试你以前写的版本，看能不能过。。。
: 我试了2个版本，加上我新写的，都过不去了。。。

c*p2013-08-07 07:08

26 楼

哦哦。。。
今天leetcode大oj就是很难过。

【在 l*******0 的大作中提到】

: A solution that could deal with dups. O(N^3).
: public ArrayList> fourSum(int[] num, int target) {
: int len=num.length;
: Arrays.sort(num);
: ArrayList> results=new ArrayList: Integer>>();
: for(int i=0;i: if(i-1>=0&&num[i]==num[i-1]) continue; //skip dup in outmost
: loop
: for(int j=i+1;j

c*p2013-08-07 07:08

27 楼

就你聪明！

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

: 笨死！你还是进尼姑庵吧～