Implementação 4sum em Java a partir do leetcode
A declaração do problema do leetcode diz:
Dada uma matriz S de n inteiros, existem elementos a, b, c e d em S tais que a + b + c + d = alvo? Encontre todos os quadrigêmeos exclusivos na matriz que dão a soma do alvo.
Nota:
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.
Sobre esse problema de quatro soma, tenho duas perguntas:
Onde eu errei? O código compilado não pode passar todos os testes, mas achei que o código deveria estar certo, pois está usando apenas a força bruta para resolver o problema.Existe alguma maneira eficiente de resolver o problema de quatro soma em vez deste algoritmo de tempo de execução O (n ^ 4)?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;
}
}