Différence entre deux algorithmes similaires de 3Sum ?

Question

J'ai trouvé le problème 3Sum sur http://www.leetcode.com/onlinejudge qui se déroule comme suit :

Étant donné un tableau S de n entiers, existe-t-il des éléments a, b, c dans S tels que a + b + c = 0 ? Trouver tous les triplets uniques dans le tableau qui donnent la somme de zéro.

Note : Les éléments d'un triplet (a,b,c) doivent être dans un ordre non décroissant. (c'est-à-dire, a b c) L'ensemble de solutions ne doit pas contenir de triplets en double.

For example, given array S = {-1 0 1 2 -1 -4},

A solution set is:
(-1, 0, 1)
(-1, -1, 2)

J'ai parcouru le site et trouvé cette suggestion de solution :

public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
    Arrays.sort(num);
    HashSet<ArrayList<Integer>> lstSoln = new HashSet<ArrayList<Integer>>();

    ArrayList<Integer> tempArr = null;
    for (int i = 0; i < num.length; i++) {
        int j = i + 1;
        int k = num.length - 1;
        while (j < k) {
            int sum3 = num[i] + num[j] + num[k];
            if (sum3 < 0) {
                j++;
            } else if (sum3 > 0) {
                k--;
            } else {
                tempArr = new ArrayList<Integer>();
                Collections.addAll(tempArr, num[i], num[j], num[k]);
                lstSoln.add(tempArr);
                j++;
                k--;
            }
        }
    }

    return new ArrayList<ArrayList<Integer>>(lstSoln);
}

Comme vous pouvez le voir, cette méthode prend tous les numéros et les suit avec deux numéros après l'indice actuel. Il est donc clair qu'une fois que le premier nombre positif est atteint, nous ne faisons que des boucles inutiles et nous ne trouverons aucun triplet s'ajoutant à 0. J'ai donc modifié la solution et ajouté une condition après for

if (num[i] > 0)
    break;

En effet, cela devrait réduire le nombre de fois où la boucle for s'exécute et donc réduire le temps nécessaire pour trouver la solution. Je l'ai même vérifié en ajoutant un compteur et en l'incrémentant à chaque fois qu'une solution est trouvée. if() . Chaque fois que le COUNTER pour ma solution est inférieur au compteur de la solution suggérée.

Cependant, lorsque j'entre ma solution modifiée dans la page de vérification, il y a soit une erreur de dépassement de temps, soit un temps plus long que la version non modifiée ! Je veux savoir ce qui ne va pas avec ma modification ?

Answer 1

Je ne vois rien d'anormal dans votre solution, j'ai essayé les deux solutions sur mon ordinateur local et celle avec la condition if ajoutée fonctionne plus rapidement. J'ai vérifié la différence de temps en utilisant System.nanotime(). Il se peut que vous soyez confronté à des erreurs de délai d'attente sur la page de vérification de la solution en raison de problèmes de réseau.