4Sum

Q: Quelle est la complexité temporelle de 4Sum ?

O(n³). Les deux boucles sélectionnent environ n²/2 paires (i, j) , et chacune fait l’objet d’un balayage à deux pointeurs d’au plus n étapes ; le tri en O(n log n) est négligeable à côté.

Q: Comment généraliser 4Sum en kSum ?

Écrivez kSum(nums, target, k) sur une liste triée. Pour k = 2, la fonction effectue un balayage à deux pointeurs. Pour une valeur de k plus grande, elle parcourt les premières valeurs, ignore les répétitions et s’appelle elle-même avec k-1 et target - nums[i] sur les valeurs situées à droite. Chaque niveau ajoute un facteur n, donc kSum coûte O(n^(k-1)).

Q: Peut-on résoudre 4Sum en O(n²) ?

Tu peux regrouper les sommes des paires dans une table de hachage et associer chaque paire aux paires dont la somme vaut target moins sa propre somme. Cette méthode est rapide lorsque peu de paires partagent une même somme, mais une somme peut contenir O(n²) paires, donc, dans le pire des cas, la complexité n’est pas meilleure que O(n³).

MoyenDeux pointeurs Tri

+10

On vous donne une liste d’entiers nums et un entier target. Renvoyez tous les quadruplets [a, b, c, d] dont les quatre valeurs se trouvent à quatre positions différentes de nums et dont la somme est égale à target. Écrivez chaque quadruplet avec ses valeurs dans l’ordre non décroissant. Si les mêmes quatre valeurs peuvent être choisies à partir de positions différentes, le quadruplet n’apparaît qu’une seule fois. Triez la réponse d’abord par première valeur, puis par deuxième, puis par troisième. Si aucun quadruplet ne convient, renvoyez une liste vide.

Fonction

fourSum(nums: integer-array, target: integer) → integer-2d-array

numsinteger-array: les nombres parmi lesquels choisir, au moins un
targetinteger: la somme que chaque quadruplet doit atteindre
Renvoieinteger-2d-array: les quadruplets distincts dont la somme est target, chacun trié, la liste étant également triée ; une liste vide s'il n'y en a aucun

Contraintes

1 ≤ nums.length ≤ 200
-10⁸ ≤ nums[i] ≤ 10⁸
-10⁹ ≤ target ≤ 10⁹
La somme de quatre valeurs quelconques est comprise entre -4 × 10⁸ et 4 × 10⁸, elle tient donc dans un entier de 32 bits.
Les quadruplets qui contiennent les mêmes quatre valeurs comptent comme un seul.

Exemples

Entrée: nums = [3, -1, 0, 2, -2, 1, -3]target = 1
Sortie: [[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]
Explication: Chacun des quatre quadruplets a une somme égale à 1, par exemple -3 + (-1) + 2 + 3. Ceux qui commencent par -3 viennent en premier, classés selon leur deuxième valeur : -1 avant 0.

Entrée: nums = [4, 4, 4, 4, 4, 4]target = 16
Sortie: [[4, 4, 4, 4]]
Explication: Les 15 choix de quatre positions parmi six donnent quatre 4 dont la somme est égale à 16, donc [4, 4, 4, 4] apparaît une fois.

Entrée: nums = [1, 5, 2, 9]target = 3
Sortie: []
Explication: Le seul choix consiste à prendre les quatre nombres, et 1 + 5 + 2 + 9 = 17, pas 3, donc la réponse est une liste vide.

Pour aller plus loin

Compte les ensembles de quatre positions dont les valeurs s’additionnent pour atteindre target, plutôt que les quadruplets distincts. Le deuxième exemple en compte 15. Peux-tu le faire en O(n²) ?

Indices

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

0 sur 3 ouverts

Solution

Vérifier chaque ensemble de quatre positions coûte O(n⁴), et les valeurs répétées construisent plusieurs fois le même quadruplet. Appliquez la réduction du 3Sum un niveau plus loin : triez, fixez les deux premières valeurs avec deux boucles, trouvez la dernière paire avec deux pointeurs et ignorez les valeurs répétées à chaque niveau.

Essayez chaque ensemble de quatre

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Triez d’abord, afin que les positions i < j < k < l contiennent des valeurs en ordre non décroissant et que chaque quadruplet soit écrit dans le bon ordre. Quatre boucles imbriquées parcourent toutes les combinaisons de quatre positions. Pour éviter les répétitions, une boucle passe à l’itération suivante lorsque la position suivante contient la valeur qu’elle a essayée à l’itération précédente. Avec six 4, chaque boucle n’essaie que sa première position, si bien que [4, 4, 4, 4] apparaît une seule fois au lieu de 15 fois.

Pour 200 nombres, il y a 64,684,950 ensembles de quatre, et ce nombre est multiplié par environ 16 quand n double.

Algorithme

Triez nums.
Imbriquez quatre boucles sur i < j < k < l, chacune commençant juste après la boucle qui l’entoure.
Dans chaque boucle, passez une position qui n’est pas la première de la boucle et qui contient la même valeur que la position précédente.
Enregistrez [nums[i], nums[j], nums[k], nums[l]] lorsque les quatre valeurs ont pour somme target. Les boucles les produisent dans l’ordre trié.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 2):
            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 - 1):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                for l in range(k + 1, n):
                    if l > k + 1 and nums[l] == nums[l - 1]:
                        continue  # same fourth value as the round before
                    if nums[i] + nums[j] + nums[k] + nums[l] == target:
                        quads.append([nums[i], nums[j], nums[k], nums[l]])
    return quads

Trier, deux boucles, deux pointeurs

Intuition

Fixez nums[i] et nums[j] : il reste alors un problème de paire : trouver deux valeurs à droite de j dont la somme est égale à target - nums[i] - nums[j]. Sur une liste triée, un seul balayage suffit. Commencez avec lo à j+1 et hi au dernier indice. Une somme inférieure à target fait avancer lo vers la droite ; une somme supérieure le fait reculer vers la gauche.

Chaque déplacement élimine une valeur qui ne peut faire partie d’aucune solution. Si la somme est trop petite, même la plus grande valeur restante, nums[hi], ne suffit pas pour nums[lo] ; nums[lo] peut donc être éliminée. Une somme trop grande élimine nums[hi] pour la raison inverse. Une paire (i, j) nécessite au plus n déplacements ; les n²/2 paires coûtent donc O(n³).

Dans le premier exemple, avec i sur -3 et j sur -1, lo avance de 0, dépasse 1 et arrive à 2, où -3 + (-1) + 2 + 3 = 1.

Algorithme

Trie nums.
Pour chaque i, ignore-le lorsque i > 0 et que nums[i] est égal à nums[i-1].
Pour chaque j après i, ignore-le lorsque j > i+1 et que nums[j] est égal à nums[j-1].
Définis lo = j+1 et hi = n-1. Tant que lo < hi, compare la somme des quatre valeurs à target : si elle est inférieure, déplace lo vers la droite ; si elle est supérieure, déplace hi vers la gauche.
En cas de correspondance, enregistre le quadruplet, déplace les deux pointeurs, puis avance lo tant qu’il contient la valeur qu’il utilisait.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # this second value was already handled
            lo, hi = j + 1, n - 1
            while lo < hi:
                total = nums[i] + nums[j] + nums[lo] + nums[hi]
                if total < target:
                    lo += 1
                elif total > target:
                    hi -= 1
                else:
                    quads.append([nums[i], nums[j], nums[lo], nums[hi]])
                    lo += 1
                    hi -= 1
                    while lo < hi and nums[lo] == nums[lo - 1]:
                        lo += 1
    return quads

Pièges et cas limites

Ignorer j chaque fois que nums[j] est égal à nums[j-1]. À j = i+1, on compare avec la valeur utilisée par i, donc [2, 2, 2, 2, 2] avec la cible 8 perd [2, 2, 2, 2].
Copier la sortie anticipée de 3Sum nums[i] > target. Avec [-5, -4, -3, -2, -1] et la cible -10, la boucle s'arrête à -5 et ne trouve pas [-4, -3, -2, -1].
Listes de moins de quatre éléments. Avec un ou deux nombres, n-3 est négatif : 0..<(n - 3) provoque un piège dans Swift, et n - 3 sur un usize Rust provoque un sous-dépassement. Renvoyer d'abord une liste vide.
Recueillir les quadruplets dans un ensemble de hachage et les renvoyer sans les trier.

Questions fréquentes3

Quelle est la complexité temporelle de 4Sum ?

O(n³). Les deux boucles sélectionnent environ n²/2 paires (i, j), et chacune fait l’objet d’un balayage à deux pointeurs d’au plus n étapes ; le tri en O(n log n) est négligeable à côté.

Comment généraliser 4Sum en kSum ?

Écrivez kSum(nums, target, k) sur une liste triée. Pour k = 2, la fonction effectue un balayage à deux pointeurs. Pour une valeur de k plus grande, elle parcourt les premières valeurs, ignore les répétitions et s’appelle elle-même avec k-1 et target - nums[i] sur les valeurs situées à droite. Chaque niveau ajoute un facteur n, donc kSum coûte O(n^(k-1)).

Peut-on résoudre 4Sum en O(n²) ?

Tu peux regrouper les sommes des paires dans une table de hachage et associer chaque paire aux paires dont la somme vaut target moins sa propre somme. Cette méthode est rapide lorsque peu de paires partagent une même somme, mais une somme peut contenir O(n²) paires, donc, dans le pire des cas, la complexité n’est pas meilleure que O(n³).

def fourSum(nums, target):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

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

Résultat attendu

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