Étant donné un tableau de nombres, savoir si trois d'entre eux ajoutent à 0

Question

Étant donné un tableau de nombres, savoir si trois d'entre eux ajoutent à 0.

Do it in N^2, comment un fais ça?

Answer 1

O (n^2) solution sans tables de hachage (parce que l'utilisation de tables de hachage est triche: P). Voici le pseudocode:

Sort the array // O(nlogn) 

for each i from 1 to len(array) - 1 
    iter = i + 1 
    reviter = len(array) - 1 
    while iter < reviter 
    tmp = array[iter] + array[reviter] + array[i] 
    if tmp > 0 
     reviter-- 
    else if tmp < 0 
     iter++ 
    else 
     return true 
return false 

Fondamentalement, en utilisant un tableau trié, pour chaque numéro (cible) dans un tableau, vous utilisez deux pointeurs, l'un à partir de l'avant et un à partir de l'arrière du tableau, vérifiez si le la somme des éléments pointés par les pointeurs est>, < ou == vers la cible, et avance les pointeurs en conséquence ou renvoie true si la cible est trouvée.

Answer 2

mettre le négatif de chaque nombre dans une table de hachage ou une autre structure de données de recherche à temps constant. (n)

boucle dans le tableau obtenant chaque ensemble de deux nombres (n^2), et voir si leur somme est dans la table de hachage.

Answer 3

Pas pour le crédit ou quoi que ce soit, mais voici ma version python de la solution de Charles Ma. Très sympa.

def find_sum_to_zero(arr): 
    arr = sorted(arr) 
    for i, target in enumerate(arr): 
     lower, upper = 0, len(arr)-1 
     while lower < i < upper: 
      tmp = target + arr[lower] + arr[upper] 
      if tmp > 0: 
       upper -= 1 
      elif tmp < 0: 
       lower += 1 
      else: 
       yield arr[lower], target, arr[upper] 
       lower += 1 
       upper -= 1 

if __name__ == '__main__': 
    # Get a list of random integers with no duplicates 
    from random import randint 
    arr = list(set(randint(-200, 200) for _ in range(50))) 
    for s in find_sum_to_zero(arr): 
     print s 

---

Beaucoup plus tard:

def find_sum_to_zero(arr): 
    limits = 0, len(arr) - 1 
    arr = sorted(arr) 
    for i, target in enumerate(arr): 
     lower, upper = limits 
     while lower < i < upper: 
      values = (arr[lower], target, arr[upper]) 
      tmp = sum(values) 
      if not tmp: 
       yield values 
      lower += tmp <= 0 
      upper -= tmp >= 0 

Answer 4

Ne pas essayer de se vanter de mes compétences en programmation ou ajouter des choses redondantes ici. Je voulais juste fournir aux débutants une implémentation en C++. Implémentation basée sur le pseudocode fourni par Charles Ma. J'espère que les commentaires aideront.

#include <iostream> 
using namespace std; 

void merge(int originalArray[], int low, int high, int sizeOfOriginalArray){ 
    // Step 4: Merge sorted halves into an auxiliary array 
    int aux[sizeOfOriginalArray]; 
    int auxArrayIndex, left, right, mid; 

    auxArrayIndex = low; 
    mid = (low + high)/2; 
    right = mid + 1; 
    left = low; 

    // choose the smaller of the two values "pointed to" by left, right 
    // copy that value into auxArray[auxArrayIndex] 
    // increment either left or right as appropriate 
    // increment auxArrayIndex 
    while ((left <= mid) && (right <= high)) { 
     if (originalArray[left] <= originalArray[right]) { 
      aux[auxArrayIndex] = originalArray[left]; 
      left++; 
      auxArrayIndex++; 
     }else{ 
      aux[auxArrayIndex] = originalArray[right]; 
      right++; 
      auxArrayIndex++; 
     } 
    } 

    // here when one of the two sorted halves has "run out" of values, but 
    // there are still some in the other half; copy all the remaining values 
    // to auxArray 
    // Note: only 1 of the next 2 loops will actually execute 
    while (left <= mid) { 
     aux[auxArrayIndex] = originalArray[left]; 
     left++; 
     auxArrayIndex++; 
    } 

    while (right <= high) { 
     aux[auxArrayIndex] = originalArray[right]; 
     right++; 
     auxArrayIndex++; 
    } 

    // all values are in auxArray; copy them back into originalArray 
    int index = low; 
    while (index <= high) { 
     originalArray[index] = aux[index]; 
     index++; 
    } 
} 

void mergeSortArray(int originalArray[], int low, int high){ 
    int sizeOfOriginalArray = high + 1; 
    // base case 
    if (low >= high) { 
     return; 
    } 

    // Step 1: Find the middle of the array (conceptually, divide it in half) 
    int mid = (low + high)/2; 

    // Steps 2 and 3: Recursively sort the 2 halves of origianlArray and then merge those 
    mergeSortArray(originalArray, low, mid); 
    mergeSortArray(originalArray, mid + 1, high); 
    merge(originalArray, low, high, sizeOfOriginalArray); 
} 

//O(n^2) solution without hash tables 
//Basically using a sorted array, for each number in an array, you use two pointers, one starting from the number and one starting from the end of the array, check if the sum of the three elements pointed to by the pointers (and the current number) is >, < or == to the targetSum, and advance the pointers accordingly or return true if the targetSum is found. 

bool is3SumPossible(int originalArray[], int targetSum, int sizeOfOriginalArray){ 
    int high = sizeOfOriginalArray - 1; 
    mergeSortArray(originalArray, 0, high); 

    int temp; 

    for (int k = 0; k < sizeOfOriginalArray; k++) { 
     for (int i = k, j = sizeOfOriginalArray-1; i <= j;) { 
      temp = originalArray[k] + originalArray[i] + originalArray[j]; 
      if (temp == targetSum) { 
       return true; 
      }else if (temp < targetSum){ 
       i++; 
      }else if (temp > targetSum){ 
       j--; 
      } 
     } 
    } 
    return false; 
} 

int main() 
{ 
    int arr[] = {2, -5, 10, 9, 8, 7, 3}; 
    int size = sizeof(arr)/sizeof(int); 
    int targetSum = 5; 

    //3Sum possible? 
    bool ans = is3SumPossible(arr, targetSum, size); //size of the array passed as a function parameter because the array itself is passed as a pointer. Hence, it is cummbersome to calculate the size of the array inside is3SumPossible() 

    if (ans) { 
     cout<<"Possible"; 
    }else{ 
     cout<<"Not possible"; 
    } 

    return 0; 
} 

Answer 5

Commencez par trier le tableau, puis, pour chaque nombre négatif (A) dans le tableau, trouvez deux éléments dans le tableau en ajoutant -A. Trouver 2 éléments dans un tableau trié qui s'ajoute au nombre donné prend le temps O (n), donc la complexité du temps entier est O (n^2).

Answer 6

Ceci est mon approche par Swift 3 en N^2 log N ...

let integers = [-50,-40, 10, 30, 40, 50, -20, -10, 0, 5] 

Première étape, trier tableau

let sortedArray = integers.sorted() 

En second lieu, mettre en œuvre une méthode de recherche binaire qui renvoie un index comme si ...

func find(value: Int, in array: [Int]) -> Int { 

    var leftIndex = 0 
    var rightIndex = array.count - 1 

    while leftIndex <= rightIndex { 

     let middleIndex = (leftIndex + rightIndex)/2 
     let middleValue = array[middleIndex] 

     if middleValue == value { 
      return middleIndex 
     } 
     if value < middleValue { 
      rightIndex = middleIndex - 1 
     } 
     if value > middleValue { 
      leftIndex = middleIndex + 1 
     } 
    } 
    return 0 
} 

Enfin, mettre en œuvre une méthode qui permet de suivre à chaque fois un ensemble de somme « triplés » 0 ...

func getTimesTripleSumEqualZero(in integers: [Int]) -> Int { 

    let n = integers.count 
    var count = 0 

    //loop the array twice N^2 
    for i in 0..<n { 
     for j in (i + 1)..<n { 
      //Sum the first pair and assign it as a negative value 
      let twoSum = -(integers[i] + integers[j]) 
      // perform a binary search log N 
      // it will return the index of the give number 
      let index = find(value: twoSum, in: integers) 
      //to avoid duplications we need to do this check by checking the items at correspondingly indexes 
      if (integers[i] < integers[j] && integers[j] < integers[index]) { 
       print("\([integers[i], integers[j], integers[index]])") 
       count += 1 
      } 
     } 
    } 
    return count 
} 

print("count:", findTripleSumEqualZeroBinary(in: sortedArray)) 

impressions --- count: 7