2 xgl112112 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>();
                        nowNode.add(nums[fixed1]);
                        nowNode.add(nums[fixed2]);
                        nowNode.add(nums[first]);
                        nowNode.add(nums[last]);
                        result.add(nowNode);
                    }


                    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>();
                        nowNode.add(nums[fixed1]);
                        nowNode.add(nums[fixed2]);
                        nowNode.add(nums[first]);
                        nowNode.add(nums[last]);
                        result.add(nowNode);
                    }


                    first++;
                    last--;
                }
            }

            fixed2++;

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

    }

两个方法唯一不同只有注释地方,方法一中的”代码1“和方法二中的”代码2“,但是性能完全不同,方法一输出1,代码二输出0,再leetcode中方法一超时,方法二ac,这是什么原因。。。。。

1个回答

devmiao
devmiao   Ds   Rxr 2016.09.19 23:51
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
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总结
题目: 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:
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