O (NlogN) recherche 3 nombres qui ont une somme de T arbitraire dans un tableau

Donné un tableau de nombres entiers, de trouver toutes les 3 d'entre eux qui, en somme à tout T.

Je l'ai vu sur certains post en ligne, qui prétend qu'il a un O(NlogN) solution.

Pour 2 numéros, je sais hashtable pourrait aider pour O(N), mais pour 3 numéros, je ne peux pas en trouver un.

J'ai aussi ce problème de sons familiers à certains des problèmes difficiles, mais ne me souviens pas le nom et ne peut donc pas google pour elle. (Pendant que le pire est évidemment O(N^3), et avec la solution à 2 chiffres, il est vraiment temps O(N^2) )

Il ne résout pas vraiment quoi que ce soit dans le monde réel, juste des bugs moi..

Une idée?

source d'informationauteur Dr. Xray

  1. 12

    Je pense que votre problème est équivalent à la 3SUM problème.

  2. 3

    Pour trois somme problème, vous ne pouvez pas trouver une solution meilleure que O(n^2). Vous pouvez vous référer à http://en.wikipedia.org/wiki/List_of_unsolved_problems_in_computer_science

  3. 2

    2SUM problème peut être résolu en O(nlgn).

    Première trier le tableau qui prend au plus O(nlgn) opérations. Maintenant à la ième itération, nous avons sélectionné l'élément a[i] et trouvez l'élément -a[i] dans la partie restante de la pile (j'.e de i+1 à n-1) et cette recherche pourrait être menée dans le cadre de la recherche binaire qui prend au plus lgn temps. Si dans l'ensemble il faudra du S(nlgn) opérations.

    Mais 3SUM problème ne peut être résolu en O(nlgn). Nous avons pu réduire à O(n^2)

  4. 0

    Sonne comme un des devoirs question...

    Si vous pouvez trouver deux valeurs d'un montant total de N mais vous souhaitez étendre la recherche à trois valeurs, ne pourriez-vous pas, pour chaque valeur M dans le jeu, regardez pour les deux valeurs d'un montant total de (N - M)? Si vous pouvez trouver deux valeurs qui, en somme à une valeur spécifique en O(log N) le temps, alors que O(N log N).

  5. 0

    Je pense que c'est juste la somme de sous-ensemble problème

    Si oui, il est NP-Complet.

    EDIT: Jamais l'esprit, il est 3sum, comme dit dans une autre réponse.

  6. -2

    Levées directement à partir https://en.wikipedia.org/wiki/3SUM

        sort(S);

    for i=0 to n-3 do

        a = S[i];
        start = i+1;

        end = n-1;

        while (start < end) do

           b = S[start];
           c = S[end];
           if (a+b+c == 0) then
              output a, b, c;
              //Continue search for all triplet combinations summing to zero.
               start = start + 1
               end = end - 1

           else if (a+b+c > 0) then
              end = end - 1;
           else
              start = start + 1;
           end
        end
     end