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

LeetCode 18 4Sum (C,C++,Java,Python)
Problem: 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
(Java)LeetCode-18. 4Sum
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: Element
leetcode解题之 18. 4Sum Java版（结果是目标值的四个数字和）
leetcode解题之 18. 4Sum Java版（结果是目标值的四个数字和）
leetcode-Java-18. 4Sum
public class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> list = new ArrayList<List<Integer>>(); int len = nums.length, to
【LeetCode-面试算法经典-Java实现】【018-4Sum（四个数的和）】
【018-4Sum（四个数的和）】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题　　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
18. 4Sum Leetcode Python
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
[C++]LeetCode: 71 4Sum && kSum总结

leetcode 18. 4Sum KSum的解决办法
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: The solution set
Leetcode 454. 4Sum II 四数之和2 解题报告
1 解题思想首先，这是一道远古之前的题的进化版： Leetcode #18 4Sum 四数之和 解题小节+K-Sum思想 但是我不想说那个题了，因为我也记不住了。。这道题意思就是ABCD四个数组，长度相同，现在问题你说分别从这四个数组中各挑一个数相加其和为0，有几种方式？首先这道题肯定不能四层循环遍历。我的做法是： 将四数转变为两个部分，首先遍历AB的组合（任意两个都可以），存下他们组合后的和的
[leetcode: Python]18.4Sum
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: The solution set mu