1. Somme de deux nombres

Étant donné un tableau d'entiers nombres et une valeur cible cible, trouvez deux indices dans le tableau dont les éléments s'additionnent pour atteindre la cible. Chaque entrée n'a qu'une seule solution, et vous ne pouvez pas utiliser le même élément deux fois.

Exemple : Avec nombres = [2, 7, 11, 15] et cible = 9, les indices 0 et 1 correspondent car 2 + 7 = 9.

Solution brute-force :

public class Solveur {
    public int[] TrouverSommeDeux(int[] nombres, int cible) {
        int[] indices = new int[0];
        for (int premier = 0; premier < nombres.Length; premier++) {
            for (int second = premier + 1; second < nombres.Length; second++) {
                if (nombres[premier] + nombres[second] == cible) {
                    return new int[] { premier, second };
                }
            }
        }
        return indices;
    }
}

Cette aproche est simple mais lente, avec une complexité O(n²). Une méthode plus efficace utilise un dictionnaire pour réduire le temps d'exécution.

Solution optimisée avec dictionnaire :

public class Solveur {
    public int[] TrouverSommeDeux(int[] nombres, int cible) {
        Dictionary<int, int> correspondances = new Dictionary<int, int>();
        for (int idx = 0; idx < nombres.Length; idx++) {
            int complement = cible - nombres[idx];
            if (correspondances.ContainsKey(complement)) {
                return new int[] { correspondances[complement], idx };
            }
            correspondances[nombres[idx]] = idx;
        }
        return new int[0];
    }
}

Cette version s'exécute en O(n) et offre une meilleure performence.

2. Addition de deux listes chaînées

Deux listes chaînées non vides représentent des nombres entiers non négatifs, avec les chiffres stockés en ordre inverse (l'unité en tête). Ajoutez-les et retourenz une nouvelle liste chaînée pour la somme.

Exemple : L'entrée (2 -> 4 -> 3) + (5 -> 6 -> 4) donne 7 -> 0 -> 8, correspondant à 342 + 465 = 807.

Solution :

public class Noeud {
    public int Valeur;
    public Noeud Suivant;
    public Noeud(int v) { Valeur = v; }
}

public class Solveur {
    public Noeud AdditionnerListes(Noeud liste1, Noeud liste2) {
        Noeud resultat = null, courant = null;
        int somme = 0;
        Noeud iter1 = liste1, iter2 = liste2;
        bool retenue = false;
        while (iter1 != null || iter2 != null || retenue) {
            int val1 = iter1 == null ? 0 : iter1.Valeur;
            int val2 = iter2 == null ? 0 : iter2.Valeur;
            somme = val1 + val2 + (retenue ? 1 : 0);
            retenue = somme >= 10;
            if (retenue) somme -= 10;
            Noeud nouveau = new Noeud(somme);
            if (resultat == null) {
                resultat = nouveau;
                courant = nouveau;
            } else {
                courant.Suivant = nouveau;
                courant = nouveau;
            }
            iter1 = iter1?.Suivant;
            iter2 = iter2?.Suivant;
        }
        return resultat;
    }
}

Cette méthode parcourt les deux listes simultanément en gérant la retenue, avec une complexité linéaire O(max(m, n)).

3. Longueur de la sous-chaîne la plus longue sans caractères répétés

Étant donné une chaîne de caractères, trouvez la longueur de la plus longue sous-chaîne sans caractères répétés.

Exemples : Pour "abcabcbb", la réponse est 3 ("abc"). Pour "bbbbb", c'est 1 ("b"). Pour "pwwkew", c'est 3 ("wke").

Solution initiale avec dictionnaire :

public class Solveur {
    public int LongueurSousChaineUnique(string chaine) {
        int longueurMax = 0;
        Dictionary<char, int> caracteresVus = new Dictionary<char, int>();
        for (int pos = 0; pos < chaine.Length; pos++) {
            if (caracteresVus.ContainsKey(chaine[pos])) {
                pos = caracteresVus[chaine[pos]] + 1;
                caracteresVus.Clear();
            }
            caracteresVus[chaine[pos]] = pos;
            longueurMax = Math.Max(longueurMax, caracteresVus.Count);
        }
        return longueurMax;
    }
}

Cette approche peut être optimisée en suivant les indices de début et de fin.

Solution améliorée avec fenêtre glissante :

public class Solveur {
    public int LongueurSousChaineUnique(string chaine) {
        int longueurMax = 0;
        int debut = 0;
        int longueurCourante = 0;
        for (int fin = 0; fin < chaine.Length; fin++) {
            int indexDoublon = chaine.IndexOf(chaine[fin], debut, longueurCourante);
            if (indexDoublon != -1) {
                longueurCourante -= (indexDoublon - debut);
                debut = indexDoublon + 1;
            } else {
                longueurCourante++;
            }
            longueurMax = Math.Max(longueurMax, longueurCourante);
        }
        return longueurMax;
    }
}

Cette version utilise une fenêtre glissante pour une complexité O(n) et une meilleure efficacité.