在Java中4sum实现从莱特code [英] 4sum implementation in Java from leetcode

问题描述

这是莱特code问题声明说：

  

给定的阵列n个整数为S，在那里元件A，B，c和d在S，从而使A + B + C + D =目标？查找数组这给目标的总和在所有独特的四胞胎。

请注意：

 元素中的一个四重（A，B，C，D）必须在非降序排列。 （即≤b≤C≤D）
该解决方案集不能包含重复的四胞胎。
 

关于这四款和问题，我有2个问题：

1. 我在哪里出了错？编译code无法通过所有的测试，但我认为，code应该是正确的，因为它只使用暴力来解决问题。
2. 有没有什么有效的办法来解决这四个和问题，而不是该为O（n ^ 4）运行时间的算法？

---

 进口的java.util.List;
进口的java.util.ArrayList;
进口java.util.Collections中;

公共类FourSumSolution {
    公众的ArrayList＆LT; ArrayList的＆LT;整数GT;＆GT; fourSum（INT [] NUM，INT目标）{
        ArrayList的＆LT; ArrayList的＆LT;整数GT;＆GT; ALIST =新的ArrayList＆LT; ArrayList的＆LT;整数GT;＆GT;（）;
        INT N = num.length;

        的for（int i = 0; I＆n种;我++）
            为（诠释J = i + 1的; J＆所述N; J ++）
                为（中间体K = J + 1; K＆其中; N; k ++）
                    为（中间体升= K + 1; L＆所述N;升++）{
                        INT总和= NUM​​ [I] + NUM [J] + NUM [K] + NUM [L];
                        如果（总和==目标）{
                            ArrayList的＆LT;整数GT; tempArray =新的ArrayList＆LT;整数GT;（）;
                            Collections.addAll（tempArray，NUM [I]，NUM [J]，NUM [K]，NUM [L]）;
                            aList.add（tempArray）;
                        }
                    }
        返回ALIST;
    }
}
 

解决方案

下面是一个为O​​（n ^ 3）解决方案

 进口java.util.Arrays中;
进口的java.util.ArrayList;
进口java.util.HashSet中;
公共类解决方案{
公众的ArrayList＆LT; ArrayList的＆LT;整数GT;＆GT; fourSum（INT [] NUM，INT目标）{
    //开始在下面输入您的Java解决方案
    //不写main（）函数

    Arrays.sort（NUM）;
    HashSet的＆LT; ArrayList的＆LT;整数GT;＆GT; HSET =新的HashSet＆LT; ArrayList的＆LT;整数GT;＆GT;（）;
    ArrayList的＆LT; ArrayList的＆LT;整数GT;＆GT;结果=新的ArrayList＆LT; ArrayList的＆LT;整数GT;＆GT;（）;
    的for（int i = 0; I＆LT; num.length;我++）{
        对于（INT J = I + 1; J＆LT; num.length; J ++）{
            对于（INT K = J + 1，L = num.length  -  1; K＆LT;升;）{
                INT总和= NUM​​ [I] + NUM [J] + NUM [K] + NUM [L];
                如果（总和＆GT;目标）{
                    L--;
                }
                否则，如果（总和＆lt;目标）{
                    ķ++;
                }
                否则，如果（总和==目标）{
                    ArrayList的＆LT;整数GT;发现=新的ArrayList＆LT;整数GT;（）;
                    found.add（NUM [I]）;
                    found.add（NUM [J]）;
                    found.add（NUM [K]）;
                    found.add（NUM [L]）;
                    如果（！hSet.contains（发现））{
                        hSet.add（发现）;
                        result.add（发现）;
                    }

                    ķ++;
                    L--;

                }
            }
        }
    }
    返回结果;
}
 

}

The problem statement from leetcode says:

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 a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.

About this four sum problem, I have 2 questions:

1. Where I went wrong? The compiled code cannot pass all the tests, but I thought the code should be right since it is only using brute force to solve the problem.
2. Is there any efficient way to solve the four sum problem instead of this O(n^4) run-time algorithm?

---

import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

public class FourSumSolution{
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target){
        ArrayList<ArrayList<Integer>> aList = new ArrayList<ArrayList<Integer>>();
        int N = num.length;

        for(int i=0; i<N; i++)
            for(int j=i+1; j<N; j++)
                for(int k=j+1; k<N; k++)
                    for(int l=k+1; l<N; l++){
                        int sum = num[i] + num[j] + num[k] + num[l];                        
                        if(sum == target){
                            ArrayList<Integer> tempArray = new ArrayList<Integer>();
                            Collections.addAll(tempArray, num[i], num[j], num[k], num[l]);
                            aList.add(tempArray);
                        }
                    }
        return aList;   
    }
}

解决方案

Here is an O(n^3) solution

import java.util.Arrays;
import java.util.ArrayList;
import java.util.HashSet;
public class Solution {
public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
    // Start typing your Java solution below
    // DO NOT write main() function

    Arrays.sort(num);
    HashSet<ArrayList<Integer>> hSet = new HashSet<ArrayList<Integer>>();
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    for (int i = 0; i < num.length; i++) {
        for (int j = i + 1; j < num.length; j++) {
            for (int k = j + 1, l = num.length - 1; k < l;) {
                int sum = num[i] + num[j] + num[k] + num[l];
                if (sum > target) {
                    l--;
                }
                else if (sum < target) {
                    k++;
                }
                else if (sum == target) {
                    ArrayList<Integer> found = new ArrayList<Integer>();
                    found.add(num[i]);
                    found.add(num[j]);
                    found.add(num[k]);
                    found.add(num[l]);
                    if (!hSet.contains(found)) {
                        hSet.add(found);
                        result.add(found);
                    }

                    k++;
                    l--;

                }
            }
        }
    }
    return result;
}

}

这篇关于在Java中4sum实现从莱特code的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！