Encontrar três elementos em uma matriz cuja sum é mais próxima de um determinado número

Dada uma matriz de inteiros, A 1 , A 2 , …, A n , incluindo negativos e positivos, e outro inteiro S. Agora precisamos encontrar três inteiros diferentes na matriz, cuja sum é mais próxima do inteiro dado S Se existe mais de uma solução, qualquer uma delas está ok.

Você pode assumir que todos os números inteiros estão dentro do intervalo int32_t e nenhum estouro aritmético ocorrerá ao calcular a sum. S não é nada especial, mas um número escolhido aleatoriamente.

Existe algum algoritmo eficiente que não seja a busca por força bruta para encontrar os três inteiros?

Existe algum algoritmo eficiente que não seja a busca por força bruta para encontrar os três inteiros?

Sim; podemos resolver isso no tempo O (n 2 )! Primeiro, considere que o problema P pode ser formulado de forma equivalente de uma maneira ligeiramente diferente, eliminando a necessidade de um “valor alvo”:

problema original P : Dado um array A de n inteiros e um valor alvo S , existe um 3-tuple de A que sum S ?

problema modificado P' : Dado um array A de n inteiros, existe um 3-tuple de A que sum zero?

Note que você pode ir desta versão do problema P' de P subtraindo seu S / 3 de cada elemento em A , mas agora você não precisa mais do valor alvo.

Claramente, se nós simplesmente testarmos todas as 3-tuplas possíveis, nós resolveríamos o problema em O (n3) – essa é a linha de base da força bruta. É possível fazer melhor? E se nós escolhermos as tuplas de uma maneira um pouco mais inteligente?

Primeiro, investimos algum tempo para ordenar o array, o que nos custa uma penalidade inicial de O (n log n). Agora nós executamos este algoritmo:

 for (i in 1..n-2) { j = i+1 // Start right after i. k = n // Start at the end of the array. while (k >= j) { // We got a match! All done. if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k]) // We didn't match. Let's try to get a little closer: // If the sum was too big, decrement k. // If the sum was too small, increment j. (A[i] + A[j] + A[k] > 0) ? k-- : j++ } // When the while-loop finishes, j and k have passed each other and there's // no more useful combinations that we can try with this i. } 

Esse algoritmo funciona colocando três pointers, i , k em vários pontos da matriz. Começo no começo e lentamente caminho até o fim. k aponta para o último elemento. j aponta para onde i comecei. Nós tentamos iterativamente sumr os elementos em seus respectivos índices, e cada vez que um dos seguintes acontece:

  • A sum está exatamente certa! Nós encontramos a resposta.
  • A sum era muito pequena. Mova j mais perto do final para selecionar o próximo maior número.
  • A sum era muito grande. Mova k mais perto do começo para selecionar o menor número seguinte.

Para cada i , os pointers de j k gradualmente se aproximam um do outro. Eventualmente eles passarão um pelo outro, e nesse ponto não precisamos tentar mais nada para isso, já que estaríamos sumndo os mesmos elementos, apenas em uma ordem diferente. Depois desse ponto, tentamos o próximo i e repetimos.

Eventualmente, ou esgotaremos as possibilidades úteis, ou encontraremos a solução. Você pode ver que isso é O (n 2 ), já que executamos o loop externo O (n) vezes e executamos o loop interno O (n) vezes. É possível fazer isso sub-quadraticamente se você ficar realmente chique, representando cada inteiro como um vetor de bits e executando uma transformação rápida de Fourier, mas isso está além do escopo desta resposta.


Nota: Como essa é uma questão de entrevista, eu trapaceei um pouco aqui: esse algoritmo permite a seleção do mesmo elemento várias vezes. Ou seja, (-1, -1, 2) seria uma solução válida, como seria (0, 0, 0). Ele também encontra apenas as respostas exatas , não a resposta mais próxima, como o título menciona. Como um exercício para o leitor, deixarei que você descubra como fazê-lo funcionar apenas com elementos distintos (mas é uma mudança muito simples) e respostas exatas (o que também é uma mudança simples).

Certamente esta é uma solução melhor porque é mais fácil de ler e, portanto, menos propensa a erros. O único problema é que precisamos adicionar algumas linhas de código para evitar a seleção múltipla de um elemento.

Outra solução O (n ^ 2) (usando um hashset).

 // K is the sum that we are looking for for i 1..n int s1 = K - A[i] for j 1..i int s2 = s1 - A[j] if (set.contains(s2)) print the numbers set.add(A[i]) 

Que tal algo como isto, que é O (n ^ 2)

 for(each ele in the sorted array) { ele = arr[i] - YOUR_NUMBER; let front be the pointer to the front of the array; let rear be the pointer to the rear element of the array.; // till front is not greater than rear. while(front < = rear) { if(*front + *rear == ele) { print "Found triplet "<<*front<<","<<*rear<<","< ele, so we need to decrease the sum by decrementing rear pointer. if((*front + *rear) > ele) decrement rear pointer. // sum is < ele, so we need to increase the sum by incrementing the front pointer. else increment front pointer. } } 

Isto encontra se sum de 3 elementos é exatamente igual ao seu número. Se você quiser mais próximo, você pode modificá-lo para lembrar o menor delta (diferença entre o número de tripleto atual) e no final imprimir o trio correspondente ao menor delta.

A solução de John Feminella tem um bug.

Na linha

 if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k]) 

Precisamos verificar se i, j, k são todos distintos. Caso contrário, se meu elemento de destino for 6 e se minha matriz de input contiver {3,2,1,7,9,0,-4,6} . Se eu imprimir as tuplas que summ 6, então eu também obteria 0,0,6 como saída. Para evitar isso, precisamos modificar a condição dessa maneira.

 if ((A[i] + A[j] + A[k] == 0) && (i!=j) && (i!=k) && (j!=k)) return (A[i], A[j], A[k]) 

Note que temos uma matriz ordenada. Essa solução é semelhante à solução de João, apenas que procura a sum e não repete o mesmo elemento.

 #include ; int checkForSum (int arr[], int len, int sum) { //arr is sorted int i; for (i = 0; i < len ; i++) { int left = i + 1; int right = len - 1; while (right > left) { printf ("values are %d %d %d\n", arr[i], arr[left], arr[right]); if (arr[right] + arr[left] + arr[i] - sum == 0) { printf ("final values are %d %d %d\n", arr[i], arr[left], arr[right]); return 1; } if (arr[right] + arr[left] + arr[i] - sum > 0) right--; else left++; } } return -1; } int main (int argc, char **argv) { int arr[] = {-99, -45, -6, -5, 0, 9, 12, 16, 21, 29}; int sum = 4; printf ("check for sum %d in arr is %d\n", sum, checkForSum(arr, 10, sum)); } 

Aqui está o código C ++:

 bool FindSumZero(int a[], int n, int& x, int& y, int& z) { if (n < 3) return false; sort(a, a+n); for (int i = 0; i < n-2; ++i) { int j = i+1; int k = n-1; while (k >= j) { int s = a[i]+a[j]+a[k]; if (s == 0 && i != j && j != k && k != i) { x = a[i], y = a[j], z = a[k]; return true; } if (s > 0) --k; else ++j; } } return false; } 

Solução muito simples N ^ 2 * logN: ordene o array de input, depois passe por todos os pares A i , A j (tempo N ^ 2) e, para cada par, verifique se (S – A i – A j ) está no array ( logN time).

Outra solução O (S * N) usa a abordagem de programação dinâmica clássica.

Em resumo:

Crie uma matriz de 2 d V [4] [S + 1]. Preencha de tal maneira que:

V [0] [0] = 1, V [0] [x] = 0;

V 1 [A i ] = 1 para qualquer i, V 1 [x] = 0 para todos os outros x

V [2] [A i + A j ] = 1, para qualquer i, j. V [2] [x] = 0 para todos os outros x

V [3] [sum de quaisquer 3 elementos] = 1.

Para preenchê-lo, faça a iteração por A i , para cada iteração de A i pela matriz, da direita para a esquerda.

Isso pode ser resolvido eficientemente em O (n log (n)) como a seguir. Eu estou dando uma solução que diz se a sum de três números é igual a um dado número.

 import java.util.*; public class MainClass { public static void main(String[] args) { int[] a = {-1, 0, 1, 2, 3, 5, -4, 6}; System.out.println(((Object) isThreeSumEqualsTarget(a, 11)).toString()); } public static boolean isThreeSumEqualsTarget(int[] array, int targetNumber) { //O(n log (n)) Arrays.sort(array); System.out.println(Arrays.toString(array)); int leftIndex = 0; int rightIndex = array.length - 1; //O(n) while (leftIndex + 1 < rightIndex - 1) { //take sum of two corners int sum = array[leftIndex] + array[rightIndex]; //find if the number matches exactly. Or get the closest match. //here i am not storing closest matches. You can do it for yourself. //O(log (n)) complexity int binarySearchClosestIndex = binarySearch(leftIndex + 1, rightIndex - 1, targetNumber - sum, array); //if exact match is found, we already got the answer if (-1 == binarySearchClosestIndex) { System.out.println(("combo is " + array[leftIndex] + ", " + array[rightIndex] + ", " + (targetNumber - sum))); return true; } //if exact match is not found, we have to decide which pointer, left or right to move inwards //we are here means , either we are on left end or on right end else { //we ended up searching towards start of array,ie we need a lesser sum , lets move inwards from right //we need to have a lower sum, lets decrease right index if (binarySearchClosestIndex == leftIndex + 1) { rightIndex--; } else if (binarySearchClosestIndex == rightIndex - 1) { //we need to have a higher sum, lets decrease right index leftIndex++; } } } return false; } public static int binarySearch(int start, int end, int elem, int[] array) { int mid = 0; while (start <= end) { mid = (start + end) >>> 1; if (elem < array[mid]) { end = mid - 1; } else if (elem > array[mid]) { start = mid + 1; } else { //exact match case //Suits more for this particular case to return -1 return -1; } } return mid; } } 

Redução: Eu acho que a solução de John Feminella O (n2) é mais elegante. Ainda podemos reduzir o A [n] no qual procurar por tupla. Observando A [k] tal que todos os elementos estariam em A [0] – A [k], quando nosso array de busca é enorme e SUM (s) realmente pequeno.

A [0] é o mínimo: – Ascendente matriz ordenada.

s = 2A [0] + A [k]: Dado s e A [] podemos encontrar A [k] usando pesquisa binária no tempo log (n).

Outra solução que verifica e falha no início:

 public boolean solution(int[] input) { int length = input.length; if (length < 3) { return false; } // x + y + z = 0 => -z = x + y final Set z = new HashSet<>(length); int zeroCounter = 0, sum; // if they're more than 3 zeros we're done for (int element : input) { if (element < 0) { z.add(element); } if (element == 0) { ++zeroCounter; if (zeroCounter >= 3) { return true; } } } if (z.isEmpty() || z.size() == length || (z.size() + zeroCounter == length)) { return false; } else { for (int x = 0; x < length; ++x) { for (int y = x + 1; y < length; ++y) { sum = input[x] + input[y]; // will use it as inverse addition if (sum < 0) { continue; } if (z.contains(sum * -1)) { return true; } } } } return false; } 

Eu adicionei alguns testes de unidade aqui: GivenArrayReturnTrueIfThreeElementsSumZeroTest .

Se o conjunto estiver usando muito espaço, posso usar facilmente um java.util.BitSet que usará o espaço O (n / w).

Aqui está o programa em java que é O (N ^ 2)

 import java.util.Stack; public class GetTripletPair { /** Set a value for target sum */ public static final int TARGET_SUM = 32; private Stack stack = new Stack(); /** Store the sum of current elements stored in stack */ private int sumInStack = 0; private int count =0 ; public void populateSubset(int[] data, int fromIndex, int endIndex) { /* * Check if sum of elements stored in Stack is equal to the expected * target sum. * * If so, call print method to print the candidate satisfied result. */ if (sumInStack == TARGET_SUM) { print(stack); } for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) { if (sumInStack + data[currentIndex] <= TARGET_SUM) { ++count; stack.push(data[currentIndex]); sumInStack += data[currentIndex]; /* * Make the currentIndex +1, and then use recursion to proceed * further. */ populateSubset(data, currentIndex + 1, endIndex); --count; sumInStack -= (Integer) stack.pop(); }else{ return; } } } /** * Print satisfied result. ie 15 = 4+6+5 */ private void print(Stack stack) { StringBuilder sb = new StringBuilder(); sb.append(TARGET_SUM).append(" = "); for (Integer i : stack) { sb.append(i).append("+"); } System.out.println(sb.deleteCharAt(sb.length() - 1).toString()); } private static final int[] DATA = {4,13,14,15,17}; public static void main(String[] args) { GetAllSubsetByStack get = new GetAllSubsetByStack(); get.populateSubset(DATA, 0, DATA.length); } } 

O problema pode ser resolvido em O (n ^ 2), estendendo o problema de 2-sum com pequenas modificações. É o vetor contendo elementos e B é a sum necessária.

int Solução :: threeSumClosest (vetor & A, int B) {

 sort(A.begin(),A.end()); int k=0,i,j,closest,val;int diff=INT_MAX; while(kval) ++i; if(B 

Eu fiz isso em n ^ 3, meu pseudocódigo está abaixo;

// Cria um hashMap com chave como Integer e valor como ArrayList // itera uma lista usando um loop for, para cada valor na lista repetir novamente a partir do próximo valor;

 for (int i=0; i< =arr.length-1 ; i++){ for (int j=i+1; j<=arr.length-1;j++){ 

// se a sum de arr [i] e arr [j] for menor que a sum desejada, então há potencial para encontrar um terceiro dígito, assim como outro for loop

  if (arr[i]+arr[j] < sum){ for (int k= j+1; k<=arr.length-1;k++) 

// neste caso, estamos agora procurando pelo terceiro valor; se a sum de arr [i] e arr [j] e arr [k] for a sum desejada, adicione-os ao HashMap, fazendo o arr [i] a chave e, em seguida, adicionando arr [j] e arr [k] em o ArrayList no valor dessa chave

  if (arr[i]+arr[j]+arr[k] == sum){ map.put(arr[i],new ArrayList()); map.get(arr[i]).add(arr[j]); map.get(arr[i]).add(arr[k]);} 

Depois disso, você agora tem um dictionary que tem todas as inputs que representam os três valores adicionando à sum desejada. Extraia todas essas inputs usando as funções do HashMap. Isso funcionou perfeitamente.