xgl112112 于 2016.09.19 23:48 提问

leetcode 18. 4Sum，奇怪的性能问题，求java大神指点
`````` public static List<List<Integer>> fourSum(int[] nums, int target) {

long firstTime = System.currentTimeMillis();
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(nums.length == 0)
return result;
Arrays.sort(nums);
List<Integer> nowNode = null;

int fixed1=0, fixed2;
int first, last;
int l = nums.length;
int sum = 0;
boolean isExist = false;

while(fixed1 <= (l - 4)){
fixed2 = fixed1 + 1;
while(fixed2 <= (l - 3)){
first = fixed2 + 1;
last = l - 1;
while(first < last){
isExist = false;
sum = nums[fixed1] + nums[fixed2] + nums[first] + nums[last];
if(sum < target){
first++;
}else if(sum > target){
last--;
}else{

for(List<Integer> templ : result){
//代码1
if(templ.get(0) == nums[fixed1] && templ.get(1) == nums[fixed2] && templ.get(2) == nums[first]
&& templ.get(3) == nums[last]){
isExist = true;
break;
}
}
if(!isExist){
nowNode = new ArrayList<Integer>();
}

first++;
last--;
}
}

fixed2++;

}
fixed1++;
}
System.out.println("先集合后数组"+(System.currentTimeMillis() - firstTime));
return result;

}

public static List<List<Integer>> fourSum1(int[] nums, int target) {
long firstTime = System.currentTimeMillis();

List<List<Integer>> result = new ArrayList<List<Integer>>();
if(nums.length == 0)
return result;
Arrays.sort(nums);
List<Integer> nowNode = null;

int fixed1=0, fixed2;
int first, last;
int l = nums.length;
int sum = 0;
boolean isExist = false;

while(fixed1 <= (l - 4)){
fixed2 = fixed1 + 1;
while(fixed2 <= (l - 3)){
first = fixed2 + 1;
last = l - 1;
while(first < last){
isExist = false;
sum = nums[fixed1] + nums[fixed2] + nums[first] + nums[last];
if(sum < target){
first++;
}else if(sum > target){
last--;
}else{

for(List<Integer> templ : result){
//代码2
if(nums[fixed1] == templ.get(0) && nums[fixed2] == templ.get(1) && nums[first] == templ.get(2)
&& nums[last] == templ.get(3)){
isExist = true;
break;
}
}
if(!isExist){
nowNode = new ArrayList<Integer>();
}

first++;
last--;
}
}

fixed2++;

}
fixed1++;
}
System.out.println("先数组后集合"+(System.currentTimeMillis() - firstTime));
return result;

}
``````

1个回答

devmiao      2016.09.19 23:51