leetcode 4sum N^3解法有时Time Limit Exceeded有时又能通过# JobHunting - 待字闺中
s*s
1 楼
如题。用的是judge large。
是什么原因呢？ code如下。或者看链接：http://pastebin.com/juCshJA6
public class Solution {
public ArrayList> fourSum(int[] num, int target) {
// Start typing your Java solution below
// DO NOT write main() function
Arrays.sort(num);
ArrayList> result = new ArrayList>
();
for (int i = 0; i < num.length - 3;) {
for (int j = i + 1; j < num.length - 2;) {
int k = j + 1;
int l = num.length - 1;
while (k < l) {
int sum = num[i] + num[j] + num[k] + num[l];
if (sum > target) {
int prev_l = num[l];
while(l > j && num[l] == prev_l) l--;
}
else if (sum < target) {
int prev_k = num[k];
while(k < num.length && num[k] == prev_k) k++;
}
else if (sum == target) {
ArrayList tmp = new ArrayList();
tmp.add(num[i]);
tmp.add(num[j]);
tmp.add(num[k]);
tmp.add(num[l]);
result.add(tmp);
while(k < num.length && num[k] == tmp.get(2)) k++;
while(l > j && num[l] == tmp.get(3)) l--;
}
}
int prev_j = num[j];
while(j < num.length - 2 && prev_j == num[j]) j++;
}
int prev_i = num[i];
while(i < num.length - 3 && prev_i == num[i]) i++;
}
return result;
}
}
是什么原因呢？ code如下。或者看链接：http://pastebin.com/juCshJA6
public class Solution {
public ArrayList
// Start typing your Java solution below
// DO NOT write main() function
Arrays.sort(num);
ArrayList
();
for (int i = 0; i < num.length - 3;) {
for (int j = i + 1; j < num.length - 2;) {
int k = j + 1;
int l = num.length - 1;
while (k < l) {
int sum = num[i] + num[j] + num[k] + num[l];
if (sum > target) {
int prev_l = num[l];
while(l > j && num[l] == prev_l) l--;
}
else if (sum < target) {
int prev_k = num[k];
while(k < num.length && num[k] == prev_k) k++;
}
else if (sum == target) {
ArrayList
tmp.add(num[i]);
tmp.add(num[j]);
tmp.add(num[k]);
tmp.add(num[l]);
result.add(tmp);
while(k < num.length && num[k] == tmp.get(2)) k++;
while(l > j && num[l] == tmp.get(3)) l--;
}
}
int prev_j = num[j];
while(j < num.length - 2 && prev_j == num[j]) j++;
}
int prev_i = num[i];
while(i < num.length - 3 && prev_i == num[i]) i++;
}
return result;
}
}