Étant donné un tableau de nombres, découvrez si 3 d'entre eux totalisent 0

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

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

Ne cherche pas à vanter mes compétences en programmation ou ajouter redondant de trucs ici.
Voulais juste fournir les débutants avec une implémentation en C++.
Mise en œuvre, selon le pseudo-code fourni par Charles Ma. J'espère que les commentaires de l'aide.

#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;
}

C'est mon approche de l'utilisation de Swift 3 en N^2 log N...

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

Première étape, sorte de tableau

let sortedArray = integers.sorted()

deuxièmement, 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, de mettre en œuvre une méthode qui conserve une trace de chaque fois qu'un ensemble de "triplets" somme 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))

imprime--- count: 7