3Sum

+10

Vous recevez une liste d’entiers nums. Trouvez chaque triplet [a, b, c] de valeurs prises à trois positions différentes de nums tel que a + b + c = 0. Écrivez chaque triplet dans l’ordre non décroissant (a ≤ b ≤ c) et ne listez chaque triplet distinct qu’une seule fois, même si plusieurs choix de positions permettent de l’obtenir. Renvoyez les triplets triés d’abord par leur première valeur, puis par leur deuxième.

Fonction

threeSum(nums: integer-array) → integer-2d-array

numsinteger-array: la liste d’entiers, comportant au moins trois éléments
Renvoieinteger-2d-array: chaque triplet distinct dont la somme est égale à 0, chacun en ordre non décroissant, la liste triée

Contraintes

3 ≤ nums.length ≤ 3000
-10⁵ ≤ nums[i] ≤ 10⁵
Au moins un triplet donne une somme de 0.
Deux triplets sont identiques lorsqu’ils contiennent les mêmes trois valeurs.

Exemples

Entrée: nums = [-2, 0, 1, 1, -1, 2]
Sortie: [[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]
Explication: -2 + 0 + 2, -2 + 1 + 1 et -1 + 0 + 1 font tous 0. [-2, 1, 1] peut utiliser la valeur 1 deux fois, car 1 se trouve à deux positions, tandis que [-1, 0, 1] peut être construit avec l’un ou l’autre 1, mais n’apparaît qu’une fois.

Entrée: nums = [0, 0, 0, 0]
Sortie: [[0, 0, 0]]
Explication: N’importe lesquels de trois des quatre zéros ont une somme égale à 0. Cela fait quatre choix de positions, mais ils donnent tous le même triplet, donc la réponse ne contient [0, 0, 0] qu’une seule fois.

+15 tests cachés à la soumission

Pour aller plus loin

Le même schéma permet de résoudre le problème 4Sum : fixe deux valeurs et utilise deux pointeurs sur le reste. Peux-tu l’écrire en O(n³) et gérer correctement les doublons à chaque niveau ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Deux éléments rendent 3Sum plus difficile qu’il n’y paraît. Vérifier chaque triplet coûte O(n³), et la réponse doit contenir chaque triplet une seule fois, même lorsque des valeurs se répètent. Le tri règle ces deux problèmes : les valeurs égales se retrouvent côte à côte, ce qui permet d’ignorer les répétitions en comparant les voisines, et une fois la plus petite valeur fixée, les deux autres forment un problème de somme de deux nombres dans une liste triée, que deux pointeurs résolvent en un seul parcours.

Essayez tous les triplets

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Triez d’abord la liste. Alors, pour trois positions quelconques i < j < k, les valeurs sont déjà dans l’ordre, nums[i] ≤ nums[j] ≤ nums[k], et un triplet est donc correctement écrit dès que vous le trouvez. Trois boucles imbriquées parcourent tous les choix de positions, donc aucun triplet ne peut être oublié.

Viennent ensuite les répétitions. Le premier exemple trié est [-2, -1, 0, 1, 1, 2], et [-1, 0, 1] peut prendre son 1 à l’indice 3 ou à l’indice 4. Chaque boucle ignore donc une position dont la valeur est égale à celle que cette même boucle a déjà essayée. Chaque boucle essaie alors une seule fois chaque valeur distincte, et chaque triplet distinct apparaît une seule fois, déjà dans l’ordre croissant. Le saut ne compare qu’avec la position précédente à l’intérieur de la même boucle, donc [-2, 1, 1] utilise toujours les deux 1.

Le coût est le problème. Il y a environ n³/6 triplets : pour 3000 nombres, cela représente 4.5 × 10^9 sommes, bien au-delà de toute limite de temps.

Algorithme

Triez nums.
Parcourez les positions avec i et ignorez i lorsque nums[i] est égal à nums[i-1].
À l’intérieur, parcourez j à partir de i+1 et ignorez j lorsque j > i+1 et que nums[j] est égal à nums[j-1].
À l’intérieur, parcourez k à partir de j+1 en appliquant la même règle d’omission, et enregistrez [nums[i], nums[j], nums[k]] lorsque les trois valeurs ont une somme égale à 0.
Renvoyez les triplets dans l’ordre où vous les avez trouvés. Ils sont déjà triés.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 1):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # same second value as the round before
            for k in range(j + 1, n):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                if nums[i] + nums[j] + nums[k] == 0:
                    triplets.append([nums[i], nums[j], nums[k]])
    return triplets

Fixe une valeur, trouve la paire avec un ensemble de hachage

Intuition

Une fois la première valeur nums[i] fixée, il vous faut deux valeurs ultérieures dont la somme est égale à -nums[i]. C’est le problème Two Sum. Parcourez les indices j à droite de i et conservez un ensemble des valeurs déjà parcourues. Pour chaque j, la valeur manquante est need = -nums[i] - nums[j]. Si need se trouve dans l’ensemble, [nums[i], need, nums[j]] a une somme égale à 0. La recherche dans un ensemble coûte O(1) en moyenne : pour un i, le coût est donc O(n), et la recherche complète coûte O(n²).

Le tri s’occupe toujours de la gestion des doublons. Ignorez un i dont la valeur est égale à celle qui le précède. Après une correspondance, avancez j au-delà de chaque copie de nums[j] : comme les première et troisième valeurs sont fixées, la valeur du milieu l’est aussi ; une autre copie ne pourrait donc que répéter le même triplet. Puisque need provient d’une position antérieure de la liste triée, need ≤ nums[j], et le triplet est dans l’ordre. Vous pouvez aussi vous arrêter dès que nums[i] > 0 : les deux valeurs suivantes sont au moins aussi grandes, donc la somme ne peut pas atteindre 0.

Un détail : à mesure que j avance, nums[j] augmente et need diminue ; les triplets pour un même i sont donc produits avec une valeur du milieu décroissante. Dans [-2, -1, 0, 1, 1, 2] avec i = 0, vous trouvez [-2, 1, 1] au deuxième 1, puis [-2, 0, 2] au 2. Inversez chaque groupe avant de l’ajouter à la réponse. Les versions C et R marquent les valeurs déjà vues dans un tableau indexé par valeur plutôt que dans un ensemble de hachage, ce qui fonctionne parce que chaque valeur se situe dans l’intervalle ±10^5.

Algorithme

Triez nums.
Pour chaque i, arrêtez-vous lorsque nums[i] > 0 et ignorez i lorsque nums[i] est égal à nums[i-1].
Commencez par un ensemble vide. Pour chaque j à partir de i+1, calculez need = -nums[i] - nums[j]. Si need est dans l’ensemble, enregistrez [nums[i], need, nums[j]] et avancez j au-delà des copies de nums[j].
Ajoutez nums[j] à l’ensemble et passez au j suivant.
Inversez les triplets trouvés pour ce i et ajoutez-les à la réponse.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # the two values after it are at least as large
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        group = []
        seen = set()  # values between position i and position j
        j = i + 1
        while j < n:
            need = -nums[i] - nums[j]
            if need in seen:
                group.append([nums[i], need, nums[j]])
                while j + 1 < n and nums[j + 1] == nums[j]:
                    j += 1
            seen.add(nums[j])
            j += 1
        # need shrinks as nums[j] grows, so this group came out backwards
        group.reverse()
        triplets.extend(group)
    return triplets

Trier et utiliser deux pointeurs

Intuition

L’ordre trié peut remplacer l’ensemble. Fixe nums[i], place lo à i+1 et hi au dernier indice, puis examine nums[i] + nums[lo] + nums[hi]. Si la somme est inférieure à 0, il te faut une valeur plus grande, donc lo avance vers la droite. Si elle est supérieure à 0, il te faut une valeur plus petite, donc hi recule vers la gauche. Si elle est exactement égale à 0, enregistre le triplet et déplace les deux pointeurs.

Aucun triplet n’est perdu. Quand la somme est inférieure à 0, nums[lo] est trop petit, même associé à la plus grande valeur restante, nums[hi] ; il ne peut donc être associé à aucune valeur encore dans l’intervalle, et le retirer ne fait rien perdre. Le cas où la somme est supérieure à 0 est symétrique : nums[hi] est trop grand, même associé à la plus petite valeur restante. À chaque étape, une valeur est définitivement retirée, donc un i coûte au plus n étapes, et la recherche complète O(n²), sans mémoire supplémentaire hormis le tri et le résultat.

Considère le tableau trié [-2, -1, 0, 1, 1, 2]. Avec i = 0 (valeur -2), lo commence à -1 et hi à 2 : la somme vaut -1, donc lo avance jusqu’à 0. Maintenant, -2 + 0 + 2 = 0 ; tu enregistres donc [-2, 0, 2] et les deux pointeurs arrivent sur les deux 1, qui donnent [-2, 1, 1]. Avec i = 1 (valeur -1), 0 et 2 donnent 1, donc hi recule jusqu’au deuxième 1, et -1 + 0 + 1 = 0 enregistre [-1, 0, 1]. La valeur 0 à i = 2 ne trouve rien, et à i = 3, la valeur est positive, donc la recherche s’arrête.

Pour les répétitions, deux règles sont nécessaires. Ignore un i dont la valeur est égale à celle qui le précède. Après une correspondance, fais avancer lo au-delà des copies de la valeur utilisée. hi n’a pas besoin de règle particulière : quand lo pointe vers une valeur plus grande, une copie de l’ancien nums[hi] donne alors une somme supérieure à 0 et s’éloigne d’elle-même. Comme i parcourt les valeurs distinctes par ordre croissant et que lo ne fait qu’avancer vers la droite, les triplets sont renvoyés dans l’ordre trié.

Algorithme

Triez nums.
Pour chaque i, arrêtez-vous lorsque nums[i] > 0 et ignorez i lorsque nums[i] est égal à nums[i-1].
Définissez lo = i+1 et hi = n-1. Tant que lo < hi, additionnez nums[i], nums[lo] et nums[hi].
Si la somme est inférieure à 0, déplacez lo vers la droite. Si elle est supérieure à 0, déplacez hi vers la gauche.
Si elle vaut 0, enregistrez le triplet, déplacez les deux pointeurs, puis faites avancer lo au-delà des copies de la valeur utilisée.
Renvoyez les triplets. Ils sont déjà triés.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # the two values after it are at least as large
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        lo, hi = i + 1, n - 1
        while lo < hi:
            total = nums[i] + nums[lo] + nums[hi]
            if total < 0:
                lo += 1
            elif total > 0:
                hi -= 1
            else:
                triplets.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
    return triplets

Pièges et cas limites

La plupart des mauvaises réponses viennent des valeurs répétées ; teste donc avec des entrées qui en contiennent.

Ignorer i lorsque nums[i] est égal à nums[i+1] conserve la dernière occurrence de chaque valeur comme premier élément, et les occurrences qui la précèdent disparaissent. Dans [-1, -1, 2], cela fait perdre [-1, -1, 2]. Compare avec la position précédente, nums[i-1].
S’arrêter lorsque nums[i] ≥ 0 au lieu de nums[i] > 0 ne détecte pas [0, 0, 0].
Supprimer les répétitions à la fin au lieu de les ignorer. Avec 3000 zéros, la boucle à deux pointeurs enregistre des millions d’occurrences de [0, 0, 0] avant tout nettoyage, et dans plusieurs langages, un ensemble de listes compare les listes par identité : les occurrences restent donc présentes malgré tout.
Utiliser deux fois la même position. Une version avec un ensemble de hachage qui le remplit d’emblée avec toute la liste transforme [-2, 1, 3] en [-2, 1, 1] en utilisant deux fois l’unique 1. Ne recherche que les valeurs aux positions que tu as déjà parcourues.
Renvoyer les triplets dans le désordre. La comparaison est exacte ; la version avec un ensemble de hachage doit donc inverser chaque groupe, et une solution qui collecte les triplets dans un ensemble doit les trier à la fin.

Questions fréquentes4

Quelle est la complexité temporelle de 3Sum ?

La solution avec tri et deux pointeurs s’exécute en O(n²). Le tri coûte O(n log n), et chacun des n choix de la première valeur nécessite un balayage en O(n). Elle nécessite O(1) d’espace supplémentaire, en dehors du tri et du résultat. Vérifier tous les triplets prend plutôt O(n³).

Comment 3Sum évite-t-il les triplets en double ?

Il trie la liste, de sorte que les valeurs égales soient côte à côte. Ensuite, il ignore une première valeur égale à celle qui la précède et, après chaque correspondance, déplace le pointeur gauche au-delà des copies de la valeur utilisée. Chaque triplet est trouvé une seule fois, à partir des premières occurrences de ses valeurs, donc aucun ensemble de résultats n’est nécessaire.

Dois-je utiliser deux pointeurs ou un ensemble de hachage pour 3Sum ?

Les deux s’exécutent en temps O(n²). La méthode des deux pointeurs ne nécessite pas de mémoire supplémentaire, et le tri vous donne directement les triplets dans l’ordre. Un ensemble de hachage nécessite une mémoire O(n) et demande de veiller à ce que les positions soient distinctes et que le résultat soit trié. L’approche avec un ensemble de hachage est importante lorsque vous ne pouvez pas trier, comme dans Two Sum, où vous renvoyez les indices d’origine.

Peut-on résoudre 3Sum plus rapidement qu’en O(n²) ?

Pas de beaucoup. Les meilleurs algorithmes connus ne font mieux que n² que de quelques facteurs logarithmiques, et de nombreux résultats de difficulté en géométrie algorithmique supposent qu’aucun algorithme n’atteint une puissance de n inférieure à 2. Ces algorithmes plus rapides sont des résultats de recherche ; la réponse attendue en entretien est donc O(n²).

Python

def threeSum(nums):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Entrée

nums = [-2, 0, 1, 1, -1, 2]

Attendu

[[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]

3Sum

Fonction

Contraintes

Exemples

Indices

Solution

Essayez tous les triplets

Fixe une valeur, trouve la paire avec un ensemble de hachage

Trier et utiliser deux pointeurs

Pièges et cas limites

Questions fréquentes4

Problèmes similaires