Addition de nombres représentés par des listes chaînées

Le problème consiste à additionner deux entiers non négatifs représentés par des listes chaînées non vides. Les chiffres sont stockés dans l'ordre inverse, chaque nœud contenant un seul chiffre. L'objectif est de calculer la somme et de la renvoyer sous la forme d'une nouvelle liste chaînée respectant le même format.

Exemple :

Entrée : l1 = [2,4,3], l2 = [5,6,4]
Sortie : [7,0,8]
Explication : 342 + 465 = 807.

Pour résoudre ce problème, il est essentiel de parcourir les deux listes simultanément tout en gérant correctement la retenue (carry). Voici une implémentation optimisée en Python utilisant la fonction native divmod pour simplifier le calcul du quotient et du reste :

class NoeudListe:
    def __init__(self, valeur=0, suivant=None):
        self.valeur = valeur
        self.suivant = suivant

class Solveur:
    def additionnerNombres(self, l1: NoeudListe, l2: NoeudListe) -> NoeudListe:
        sentinelle = NoeudListe()
        curseur = sentinelle
        retenue = 0

        while l1 is not None or l2 is not None or retenue > 0:
            val_a = l1.valeur if l1 else 0
            val_b = l2.valeur if l2 else 0

            somme_intermediaire = val_a + val_b + retenue
            retenue, chiffre = divmod(somme_intermediaire, 10)

            curseur.suivant = NoeudListe(chiffre)
            curseur = curseur.suivant

            if l1: l1 = l1.suivant
            if l2: l2 = l2.suivant

        return sentinelle.suivant

Recherche d'une paire avec une somme cible dans un tableau

Étant donné un tableau d'entiers et une valeur cible, la tâche est de localiser les indices de deux éléments dont la somme correspond exactement à la cible. Chaque entrée garantit une solution unique, et un même élément ne peut être utilisé deux fois dans le calcul.

Approche par Table de Hachage en Python

Une approche naïve en O(n²) consiste à tester toutes les combinaisons possibles. Pour atteindre une complexité temporelle de O(n), l'utilisation d'un dictionnaire (table de hachage) est fortement recommandée. Il permet de stocker les éléments parcourus et de vérifier en temps consatnt si le complément nécessaire existe déjà dans la structure de données.

class Solution:
    def trouverDeuxSommes(self, nombres: list[int], cible: int) -> list[int]:
        registre_indices = {}

        for position, valeur_actuelle in enumerate(nombres):
            complement_requis = cible - valeur_actuelle

            if complement_requis in registre_indices:
                return [registre_indices[complement_requis], position]

            registre_indices[valeur_actuelle] = position

        return []

Utilisation des fonctions enumerate() et index()

La fonction native enumerate() est particulièrement utile pour ce type d'algorithme. Elle associe automatiquement un index à chaque élément d'un itérable :

# Syntaxe : enumerate(sequence, [start=0])
ma_liste = ['a', 'b', 'c']
for idx, val in enumerate(ma_liste):
    print(f"Index: {idx}, Valeur: {val}")

Bien que la méthode index() puisse récupérer la position d'un élément (par exemple nums.index(2)), elle parcourt la liste à chaque appel, ce qui dégrade considérablement les performances (complexité O(n²) si utilisée dans une boucle). De plus, elle renvoie toujours la première occurrence, rendant la gestion des doublons extrêmement complexe.

Implémentation optimisée en Langage C

En C, l'absence de table de hachage native dans la bibliothèque standard rend l'approche O(n) complexe à mettre en œuvre sans risquer des erreurs de segmentation dues aux grandes valeurs (la contrainte indique des nombres allant jusqu'à 10^9). Une alternative robuste et sans consommation excessive de mémoire consiste à utiliser l'algorithme des deux pointeurs après un tri, offrant une complexité en O(n log n).

Pour conserver les indices originaux après le tri, nous encapsulons les valeurs dans une structure :

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int valeur;
    int index_original;
} Element;

// Fonction de comparaison pour qsort
int comparer(const void* a, const void* b) {
    return ((Element*)a)->valeur - ((Element*)b)->valeur;
}

int* trouverDeuxSommesC(int* nums, int numsSize, int target, int* returnSize) {
    // Allocation et copie des données avec leurs indices
    Element* elements = (Element*)malloc(numsSize * sizeof(Element));
    if (!elements) {
        *returnSize = 0;
        return NULL;
    }
    
    for (int i = 0; i < numsSize; i++) {
        elements[i].valeur = nums[i];
        elements[i].index_original = i;
    }

    // Tri du tableau de structures
    qsort(elements, numsSize, sizeof(Element), comparer);

    int* resultats = (int*)malloc(2 * sizeof(int));
    if (!resultats) {
        free(elements);
        *returnSize = 0;
        return NULL;
    }

    int gauche = 0;
    int droite = numsSize - 1;

    // Algorithme des deux pointeurs
    while (gauche < droite) {
        int somme = elements[gauche].valeur + elements[droite].valeur;
        
        if (somme == target) {
            resultats[0] = elements[gauche].index_original;
            resultats[1] = elements[droite].index_original;
            *returnSize = 2;
            free(elements);
            return resultats;
        } else if (somme < target) {
            gauche++;
        } else {
            droite--;
        }
    }

    // Nettoyage en cas d'échec
    free(elements);
    free(resultats);
    *returnSize = 0;
    return NULL;
}
</stdlib.h></stdio.h>

Cette implémentation alloue dynamiquement la mémoire pour stocker les paires de valeurs et d'indices, garantissant qu'aucune limite arbitraire de taille de tableau (comme un tableau fixe de 100 000 éléments) ne provoquera d'erreurs d'accès mémoire face aux grandes valeurs cibles. La libération systématique de la mémoire avec free() assure l'intégrité de l'application.