Find Pivot Index

+10

Vous recevez un tableau d’entiers nums. Un indice pivot est un indice où la somme des valeurs à sa gauche est égale à la somme des valeurs à sa droite. La valeur à l’indice pivot lui-même n’appartient à aucun des deux côtés, et la somme d’un côté sans valeur est égale à 0.

Renvoyez l’indice pivot le plus à gauche, ou -1 si aucun indice n’est un pivot.

Fonction

pivotIndex(nums: integer-array) → integer

numsinteger-array: le tableau d’entiers à équilibrer
Renvoieinteger: l’indice du pivot le plus à gauche, ou -1 s’il n’y en a aucun

Contraintes

1 ≤ nums.length ≤ 10⁴
-1000 ≤ nums[i] ≤ 1000

Exemples

Entrée: nums = [3, 1, 5, 2, 2]
Sortie: 2
Explication: À l’indice 2, le côté gauche vaut 3 + 1 = 4 et le côté droit vaut 2 + 2 = 4. Les indices 0 et 1 ne sont pas équilibrés (gauche 0 contre 10, gauche 3 contre 9), donc 2 est le pivot le plus à gauche.

Entrée: nums = [1, 2, 3]
Sortie: -1
Explication: Les trois candidats donnent 0 contre 5, 1 contre 3 et 3 contre 0. Aucun indice ne s’équilibre, donc la réponse est -1.

+17 tests cachés à la soumission

Pour aller plus loin

Peux-tu trouver le pivot le plus à gauche en ne lisant chaque valeur qu’une seule fois, sans calculer d’abord la somme totale ? Quel est le coût en mémoire ?

Indices

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

0 sur 3 ouverts

Solution

Vérifier un indice nécessite deux sommes, mais les recalculer à chaque indice fait croître le travail avec le carré de la longueur. La solution consiste à arrêter de les recalculer : la somme de gauche augmente d’une valeur à chaque étape, et la somme de droite correspond à ce qu’il reste du total. Un premier parcours pour calculer le total, puis un second avec une somme cumulée à gauche, permettent de trouver le pivot le plus à gauche, avec deux nombres en mémoire.

Additionnez les deux côtés à chaque indice

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Suivez la définition. Pour chaque indice i, additionnez les valeurs qui le précèdent, additionnez celles qui le suivent, puis comparez les deux sommes. Le premier indice pour lequel les deux sommes sont égales est la réponse, car vous parcourez les indices de gauche à droite.

Les bords se gèrent tout seuls. À l’indice 0, la boucle de gauche s’exécute zéro fois, donc la somme de gauche vaut 0 ; au dernier indice, la boucle de droite s’exécute zéro fois. C’est pourquoi [4, -4, 9] renvoie 2.

Le coût est le problème. Pour chaque indice, on additionne les n-1 autres valeurs, donc le travail total représente environ n² additions. Avec 10 000 valeurs, cela représente près de 100 millions d’additions, dont la plupart répètent des sommes déjà calculées un indice plus tôt.

Algorithme

Parcourez chaque indice de nums avec i.
Additionnez les valeurs de nums[0] à nums[i-1] pour obtenir la somme à gauche.
Additionnez les valeurs de nums[i+1] à la dernière valeur pour obtenir la somme à droite.
Si les deux sommes sont égales, renvoyez i.
Si aucun indice ne correspond, renvoyez -1.

def pivotIndex(nums):
    n = len(nums)
    for i in range(n):
        left = 0
        for j in range(i):
            left += nums[j]
        right = 0
        for j in range(i + 1, n):
            right += nums[j]
        if left == right:
            return i
    return -1

Tableau des sommes préfixes

Intuition

La méthode par force brute additionne les sommes successives du tableau. Un tableau de sommes préfixes effectue ce travail une seule fois. Soit prefix[k] la somme des k premières valeurs, avec prefix[0] = 0. Pour [3, 1, 5, 2, 2], on obtient [0, 3, 4, 9, 11, 13].

Chaque somme sur une portion est maintenant la différence entre deux éléments. La partie gauche de l’indice i correspond aux i premières valeurs : c’est donc prefix[i]. La partie droite comprend tout ce qui se trouve après nums[i], soit prefix[n] - prefix[i+1]. À l’indice 2, on obtient 4 à gauche et 13 - 9 = 4 à droite : c’est un pivot.

La construction du tableau nécessite un seul parcours et chaque vérification s’effectue en temps constant ; la recherche complète est donc en O(n). En contrepartie, elle nécessite n+1 nombres supplémentaires en mémoire.

Algorithme

Crée un prefix de longueur n+1 avec prefix[0] = 0.
Remplis-le : prefix[k+1] = prefix[k] + nums[k].
Pour chaque indice i, lis la somme de gauche comme prefix[i] et la somme de droite comme prefix[n] - prefix[i+1].
Renvoie le premier i où elles sont égales, ou -1 après la boucle.

def pivotIndex(nums):
    n = len(nums)
    # prefix[k] is the sum of the first k values.
    prefix = [0] * (n + 1)
    for k in range(n):
        prefix[k + 1] = prefix[k] + nums[k]
    for i in range(n):
        left = prefix[i]
        right = prefix[n] - prefix[i + 1]
        if left == right:
            return i
    return -1

Somme totale et somme cumulée à gauche

Intuition

Regardez quelles entrées du tableau des sommes préfixes l’approche précédente lit. À l’index i, elle a besoin de prefix[i], prefix[i+1] et prefix[n]. La dernière est le total, qui ne change jamais, et les deux autres correspondent à la somme cumulée que vous obtiendriez en parcourant le tableau une seule fois. Vous pouvez donc conserver le total et une seule somme cumulée à gauche au lieu de tout le tableau.

Chaque valeur se trouve à gauche, au pivot ou à droite. La somme à droite est donc le total moins la somme à gauche moins nums[i]. Pour [3, 1, 5, 2, 2], le total est 13. À l’index 0, la somme à gauche est 0 et la somme à droite est 13 - 0 - 3 = 10. À l’index 1, elle est de 3 contre 9. À l’index 2, elle est de 4 contre 13 - 4 - 5 = 4 ; vous renvoyez donc 2.

L’ordre des opérations dans la boucle est important. Comparez d’abord, puis ajoutez nums[i] à la somme à gauche, afin que celle-ci n’inclue jamais la valeur à l’index que vous testez. En renvoyant le résultat dès la première correspondance, vous obtenez le pivot le plus à gauche.

Vous parcourez le tableau deux fois, une fois pour calculer le total et une fois pour le balayage ; le temps d’exécution est donc O(n). Seuls deux nombres sont stockés, l’espace supplémentaire est donc de O(1).

Algorithme

Ajoutez toutes les valeurs dans total.
Définissez left à 0.
Pour chaque indice i, si left est égal à total - left - nums[i], renvoyez i.
Sinon, ajoutez nums[i] à left et passez à la suite.
Si la boucle se termine, renvoyez -1.

def pivotIndex(nums):
    total = sum(nums)
    left = 0
    for i, value in enumerate(nums):
        # Everything that is not on the left and not nums[i] is on the right.
        if left == total - left - value:
            return i
        left += value
    return -1

Pièges et cas limites

La plupart des mauvaises réponses placent la valeur du pivot elle-même d’un côté ou omettent un indice de bord.

Ajouter nums[i] à la somme de gauche avant la comparaison. Le côté gauche inclut alors la valeur du pivot, et [3, 1, 5, 2, 2] ne trouve plus l’indice 2.
Calculer le côté droit avec total - left. Cela compte nums[i] du côté droit ; il faut aussi le soustraire.
Omettre l’indice 0 ou le dernier indice. L’un comme l’autre peut être le pivot, car la somme d’un côté vide vaut 0. [1, -1, 1] renvoie 0 et [4, -4, 9] renvoie 2.
Renvoyer la dernière correspondance au lieu de la première. Dans [0, 0, 0], tous les indices équilibrent les sommes, et la réponse est 0.
Utiliser deux pointeurs qui avancent depuis les deux extrémités vers le centre et agrandissent le côté le plus petit. Cela ne fonctionne que lorsque toutes les valeurs sont non négatives ; ici, les valeurs descendent jusqu’à -1000, donc un côté peut rétrécir au fur et à mesure qu’il s’agrandit.
Oublier que les tableaux Lua et R commencent à 1. Renvoyez i-1 pour obtenir un indice basé sur 0.

Questions fréquentes4

Quelle est la complexité temporelle de Find Pivot Index ?

La solution avec le total et la somme cumulée s’exécute en temps O(n) : un parcours pour additionner le tableau et un autre pour le parcourir. Elle utilise un espace supplémentaire de O(1). Recalculer les deux côtés à chaque indice prend plutôt un temps de O(n²).

Pourquoi la somme à droite est-elle égale au total moins la somme à gauche moins nums[i] ?

Chaque valeur du tableau se trouve exactement à l’un de ces trois endroits : à gauche de i, à i ou à droite de i. Leurs sommes donnent le total ; la somme de droite est donc le total auquel on a retiré les deux autres parties. Cela vous permet de vérifier un indice sans jamais additionner les valeurs à droite.

Peut-on résoudre Find Pivot Index avec deux pointeurs ?

Pas de manière fiable. Un parcours à deux pointeurs qui agrandit toujours le côté le plus petit suppose que l’ajout d’une valeur rend un côté plus grand, ce qui ne fonctionne plus dès que les valeurs peuvent être négatives : un côté peut rétrécir alors qu’on l’agrandit, et le parcours peut donc déplacer un pointeur au-delà du véritable pivot. La méthode de la somme cumulée ne fait aucune hypothèse sur les signes et vérifie chaque indice.

Quel est l’indice pivot d’un tableau contenant un seul élément ?

C’est 0. Les deux côtés de l’unique élément sont vides, et un côté vide a une somme de 0, donc les deux côtés sont égaux. La solution utilisant la somme cumulée renvoie 0 lors de sa première comparaison : la somme de gauche est 0 et le total moins 0 moins la valeur est également égal à 0.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

nums = [3, 1, 5, 2, 2]

Attendu

Find Pivot Index

Fonction

Contraintes

Exemples

Indices

Solution

Additionnez les deux côtés à chaque indice

Tableau des sommes préfixes

Somme totale et somme cumulée à gauche

Pièges et cas limites

Questions fréquentes4

Problèmes similaires