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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!