Longest Subarray with Sum K

+10

Étant donné les entiers nums et une cible k, renvoie la longueur du plus long sous-tableau dont la somme des éléments est exactement égale à k. Un sous-tableau est une suite d’éléments consécutifs d’au moins un élément. Certaines valeurs peuvent être nulles ou négatives. Si aucun sous-tableau n’a une somme égale à k, renvoie 0.

Fonction

longestSubarrayWithSumK(nums: integer-array, k: integer) → integer

numsinteger-array: les entiers à rechercher, y compris les nombres négatifs et les zéros
kinteger: la somme exacte que le sous-tableau doit avoir
Renvoieinteger: la longueur du plus long sous-tableau dont la somme est égale à k, ou 0 si aucun n’existe

Contraintes

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
-10⁹ ≤ k ≤ 10⁹
Chaque somme préfixe reste comprise entre -2 × 10⁸ et 2 × 10⁸, donc des entiers sur 32 bits suffisent.
Renvoyez 0 lorsqu’aucun sous-tableau n’a une somme égale à k.

Exemples

Entrée: nums = [2, -1, 3, 1, -4, 2, 3]k = 5
Sortie: 5
Explication: Trois séquences donnent un total de 5 : [2, 3] à la fin, [2, -1, 3, 1] au début et [3, 1, -4, 2, 3] aux indices 2 à 6. La dernière est la plus longue, avec 5 éléments.

Entrée: nums = [4, 1, 1, 2, -1, 1]k = 3
Sortie: 4
Explication: [1, 1, 2, -1] aux indices 1 à 4 et [1, 2, -1, 1] aux indices 2 à 5 ont tous deux une somme de 3 avec 4 éléments. Tu renvoies une longueur, donc l’égalité n’a pas d’importance.

Pour aller plus loin

Comment trouveriez-vous le sous-tableau contigu le plus long dont la somme est au plus k, tout en autorisant les valeurs négatives ?

Indices

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

0 sur 3 ouverts

Solution

Les sommes cumulées réduisent la somme de n’importe quel sous-tableau à une seule soustraction : les éléments après l’index s jusqu’à l’index i totalisent prefix[i] - prefix[s]. Mémorise le premier index auquel chaque total apparaît, et un seul parcours permet de trouver la plus longue correspondance se terminant à chaque position.

Étendez chaque sous-tableau à partir de chaque position de départ

Correcte, mais ne termine pas sur les plus gros tests

Intuition

À partir de chaque début, étendez vers la droite et ajoutez chaque élément à un total cumulatif. Chaque fois que le total est égal à k, notez la longueur. Chaque sous-tableau correspond à une paire de début et de fin, donc aucun n'est oublié. Continuez à étendre même après que le total dépasse k : à partir de l'indice 2 dans le premier exemple, les totaux sont 3, 4, 0, 2, 5, et c'est le -4 qui explique pourquoi le dernier atteint 5.

Il y a environ n²/2 paires : 2 × 10^8 additions pour n = 2 × 10^4.

Algorithme

Définis best sur 0.
Pour chaque start, définis total sur 0.
Déplace end de start jusqu'au dernier indice et ajoute nums[end] à total.
Lorsque total est égal à k, définis best comme étant le plus grand de best et end - start + 1.
Retourne best.

def longestSubarrayWithSumK(nums, k):
    n = len(nums)
    best = 0
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            # A match may come after the total has passed k, so never stop early
            if total == k and end - start + 1 > best:
                best = end - start + 1
    return best

Sommes préfixes avec le premier indice de chaque somme

Intuition

Un segment se terminant à l’indice i a pour somme k exactement lorsqu’un total antérieur est égal à prefix - k. Si plusieurs totaux antérieurs conviennent, le premier commence le segment le plus long ; la table ne stocke donc chaque total que lors de sa première apparition. Une occurrence ultérieure ne pourrait commencer qu’un segment plus court. Initialisez la table avec le total 0 à l’indice -1, afin qu’une correspondance commençant à l’indice 0 ait une longueur de i + 1.

Dans le premier exemple, les totaux sont 2, 1, 4, 5, 1, 3, 6. À l’indice 6, 6 - 5 = 1 est apparu pour la première fois à l’indice 1, ce qui donne une longueur de 5. Le total 1 réapparaît à l’indice 4, et conserver l’indice 1 permet de trouver ce segment.

Une recherche par élément donne un temps O(n), et la table contient au plus n + 1 totaux.

Algorithme

Crée une map first contenant le total 0 à l’index -1, et définis prefix et best à 0.
Pour chaque index i, ajoute nums[i] à prefix.
Si prefix - k se trouve dans la map à l’index start, définis best comme étant le plus grand de best et i - start.
Si prefix ne se trouve pas encore dans la map, enregistre-le avec l’index i.
Renvoie best.

def longestSubarrayWithSumK(nums, k):
    # first[p] is the index where the prefix sum p first appears; the empty prefix sits at -1
    first = {0: -1}
    prefix = 0
    best = 0
    for i, num in enumerate(nums):
        prefix += num
        # The earliest prefix equal to prefix - k starts the longest match that ends at i
        start = first.get(prefix - k)
        if start is not None and i - start > best:
            best = i - start
        # Keep the first index only: a later one could only start a shorter subarray
        if prefix not in first:
            first[prefix] = i
    return best

Pièges et cas limites

Écraser l’indice mémorisé chaque fois qu’un total se répète conserve le début le plus récent et trouve une correspondance plus courte. Le premier exemple renvoie 4 au lieu de 5, car total 1 passe de l’indice 1 à l’indice 4.
Une fenêtre qui rétrécit tant que sa somme est supérieure à k renvoie également 4 dans le premier exemple. Elle finit par contenir [-1, 3, 1, -4, 2, 3], dont la somme est 4, et ne retire jamais le -1.
Ne pas inclure le total 0 à l’indice -1 fait manquer toutes les correspondances qui commencent à l’indice 0 : [5, 0, 0, 0] avec k = 5 renvoie 0 au lieu de 4.
L’indice mémorisé correspond à la position précédant le sous-tableau, donc sa longueur est i - start. Ajouter 1 compte un élément de trop.

Questions fréquentes3

Quelle est la complexité temporelle du plus long sous-tableau dont la somme est K ?

Un temps O(n) et un espace supplémentaire O(n) avec des totaux cumulés et une map des premiers index : une recherche et au plus une insertion par élément. Faire croître chaque sous-tableau à partir de chaque début coûte un temps O(n²) et un espace O(1).

Pourquoi une fenêtre glissante échoue-t-elle lorsque le tableau contient des nombres négatifs ?

Une fenêtre glissante suppose que l’ajout d’un élément augmente la somme et que sa suppression la diminue. Avec des valeurs négatives, une fenêtre dont la somme est trop élevée peut tout de même atteindre k lorsqu’un élément négatif arrive, et une fenêtre dont la somme est trop faible peut devoir supprimer un élément négatif à sa gauche. La fenêtre ne peut pas savoir quel déplacement est le bon.

Peut-on résoudre le problème du plus long sous-tableau dont la somme est égale à K avec un espace supplémentaire en O(1) ?

Uniquement lorsqu’aucune valeur n’est négative. Alors, la somme ne diminue jamais à mesure que la fenêtre s’agrandit, et deux pointeurs trouvent la fenêtre la plus longue dont la somme est k en O(n) temps et O(1) espace. Avec des valeurs négatives, il faut la map des totaux ou le parcours en O(n²).

def longestSubarrayWithSumK(nums, k):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

nums = [2, -1, 3, 1, -4, 2, 3]
k = 5

Résultat attendu