c********p
发帖数: 1969 | 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********y
发帖数: 1559 | |
c********p
发帖数: 1969 | 3 过不去了，我写的就是这个。。。
你去试试你以前写的版本，看能不能过。。。
我试了2个版本，加上我新写的，都过不去了。。。
【在 l********y 的大作中提到】
: 照着2sum写。o(n^3)
|
s*******n
发帖数: 305 | |
z****e
发帖数: 54598 | 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;i
for(int j=i+1;j
int k=j+1,l=num.length-1;
while(k
if(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(k
while(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****e
发帖数: 54598 | 6 java要弄清楚hashtable和hashmap的区别
这是基础题，leetcode显然是用hashmap合适
hashset会自动删除重复数据，不需要你去check
直接压进去就行了 |
g**4
发帖数: 863 | 7 我的大小都能过，就是按照3sum写的
【在 c********p 的大作中提到】
: 过不去了，我写的就是这个。。。
: 你去试试你以前写的版本，看能不能过。。。
: 我试了2个版本，加上我新写的，都过不去了。。。
|
c********p
发帖数: 1969 | 8 你发来看看嘛。
【在 g**4 的大作中提到】
: 我的大小都能过，就是按照3sum写的
|
c********p
发帖数: 1969 | 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 ArrayList
Integer>>();
HashSet> set = new HashSet>();
if(num == null || num.length < 4){
return result;
}
Arrays.sort(num);
Hashtable> tab = new Hashtable
ArrayList>();
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********p
发帖数: 1969 | 10 去试试你的，我用你的也过不了。。。
难道是我的问题？
rp不行？
【在 z****e 的大作中提到】
: java要弄清楚hashtable和hashmap的区别
: 这是基础题，leetcode显然是用hashmap合适
: hashset会自动删除重复数据，不需要你去check
: 直接压进去就行了
|
|
|
z****e
发帖数: 54598 | 11 那就多刷几次
应该是jvm在你测试的过程中启动了一下gc
导致时间超时
leetcode现在刷的人太多了
内存不够用了
【在 c********p 的大作中提到】
: 去试试你的，我用你的也过不了。。。
: 难道是我的问题？
: rp不行？
|
c********p
发帖数: 1969 | 12 你的，我刷了3次，就一次过了。。。。囧。。。
另外你程序里有个地方写错了，但不影响结果。因为用了hashset。
while后边的 k == k+1, 这个不对吧。。。还有下边那个l == l+1
【在 z****e 的大作中提到】
: 那就多刷几次
: 应该是jvm在你测试的过程中启动了一下gc
: 导致时间超时
: leetcode现在刷的人太多了
: 内存不够用了
|
c********p
发帖数: 1969 | |
c********p
发帖数: 1969 | 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 Hashtable
ArrayList>();
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****e
发帖数: 54598 | 15 那两行删掉就是了，之前写3sum时候留下的
【在 c********p 的大作中提到】
: 你的，我刷了3次，就一次过了。。。。囧。。。
: 另外你程序里有个地方写错了，但不影响结果。因为用了hashset。
: while后边的 k == k+1, 这个不对吧。。。还有下边那个l == l+1
|
z****e
发帖数: 54598 | 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**4
发帖数: 863 | 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;j
int a = num[j];
// 3sum
for (int i=j+1;i
int 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********p
发帖数: 1969 | 18 哦，那个是我测试用的。。。。
【在 z****e 的大作中提到】
: 怎么还有system.out.
: 那两行如果你想写上去的话，那就是，会快一点点
: while(k: while(l>k&&num[l]==num[l+1]) l--;
|
c********p
发帖数: 1969 | 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****e
发帖数: 54598 | 20 java就是把简单的变复杂，把复杂的变简单
写hello world的话，java是最麻烦的
【在 c********p 的大作中提到】
: 哭了，c+＋可以飘过了。
: 我用java写。经常把c++代码直接翻译过来发现过不了大oj。
|
|
|
c********p
发帖数: 1969 | 21 快看看我的复杂度是多少。。。
是o(n(^2)么？
【在 z****e 的大作中提到】
: java就是把简单的变复杂，把复杂的变简单
: 写hello world的话，java是最麻烦的
|
z****e
发帖数: 54598 | 22 不止吧，我依稀看到了三重循环在里面
【在 c********p 的大作中提到】
: 快看看我的复杂度是多少。。。
: 是o(n(^2)么？
|
c********p
发帖数: 1969 | 23 是哦，同样是3层，还是你的方法简洁。。。
【在 z****e 的大作中提到】
: 不止吧，我依稀看到了三重循环在里面
|
l*******0
发帖数: 63 | 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 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
if(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(left
int 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(left
left-1]) left++; //skip dup
while(left
right]) right--; //skip dup
}else if(sum
left++;
}else{
right--;
}
}
}
}
return results;
} |
f****p
发帖数: 18483 | 25 笨死！你还是进尼姑庵吧～
【在 c********p 的大作中提到】
: 过不去了，我写的就是这个。。。
: 你去试试你以前写的版本，看能不能过。。。
: 我试了2个版本，加上我新写的，都过不去了。。。
|
c********p
发帖数: 1969 | 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********p
发帖数: 1969 | 27 就你聪明！
【在 f****p 的大作中提到】
: 笨死！你还是进尼姑庵吧～
|
u*****o
发帖数: 1224 | 28 这题没做过，只好飘过。。甜甜加油！
【在 c********p 的大作中提到】
: 快看看我的复杂度是多少。。。
: 是o(n(^2)么？
|
u*****o
发帖数: 1224 | 29 他逗你呢啊。。你就笑笑呗。。。
【在 c********p 的大作中提到】
: 就你聪明！
|
c********p
发帖数: 1969 | 30 哈哈我知道，他追着我的帖子跑。。
嘻嘻你id是说你是超级大波妹？
哈哈哈。。。
【在 u*****o 的大作中提到】
: 他逗你呢啊。。你就笑笑呗。。。
|
|
|
u*****o
发帖数: 1224 | 31 囧了。。是超声波的意思啊。。被你一说伦家都不好意思了。。
【在 c********p 的大作中提到】
: 哈哈我知道，他追着我的帖子跑。。
: 嘻嘻你id是说你是超级大波妹？
: 哈哈哈。。。
|
c********p
发帖数: 1969 | 32 哦哦。
你搞电磁的还是物理的。
我孤陋寡闻了。
【在 u*****o 的大作中提到】
: 囧了。。是超声波的意思啊。。被你一说伦家都不好意思了。。
|
c********p
发帖数: 1969 | 33 哦哦。
你搞电磁的还是物理的。
我孤陋寡闻了。
【在 u*****o 的大作中提到】
: 囧了。。是超声波的意思啊。。被你一说伦家都不好意思了。。
|
t*******e
发帖数: 274 | 34 为什么要有这两句呢？既然用了hashset应该不用去重复了吧？
【在 z****e 的大作中提到】
: 怎么还有system.out.
: 那两行如果你想写上去的话，那就是，会快一点点
: while(k: while(l>k&&num[l]==num[l+1]) l--;
|
