Résoudre Two Sum en C# : de la force brute aux tables de hachage

01 / Comprendre le problème

Étant donné un tableau d'entiers et une cible, renvoyez deux indices distincts dont la somme des valeurs atteint la cible. Sans paire, renvoyez un tableau vide. On suppose ici que les valeurs et opérations tiennent dans un entier signé sur 32 bits.

nums = [2, 7, 11, 15], cible = 9 donne [0, 1]. Un même indice ne peut pas être réutilisé.

02 / Réfléchir avant de coder

Énumérez les paires possibles. Quelle information permettrait d'éviter une nouvelle recherche complète pour chaque valeur ?

03 / Concevoir la solution

Parcourez le tableau de gauche à droite. Calculez le complément. S'il est déjà présent dans le dictionnaire, renvoyez son indice et l'indice actuel. Sinon, mémorisez la valeur actuelle.

04 / Implémenter

public static int[] TwoSumBrute(int[] nums, int target)
{
    for (int i = 0; i < nums.Length; i++)
        for (int j = i + 1; j < nums.Length; j++)
            if (nums[i] + nums[j] == target)
                return new[] { i, j };
    return Array.Empty<int>();
}

public static int[] TwoSum(int[] nums, int target)
{
    var seen = new Dictionary<int, int>();
    for (int i = 0; i < nums.Length; i++)
    {
        int complement = target - nums[i];
        if (seen.TryGetValue(complement, out int previous))
            return new[] { previous, i };
        seen[nums[i]] = i;
    }
    return Array.Empty<int>();
}

05 / Tester

TwoSum(new[] { 2, 7, 11, 15 }, 9); // [0, 1]
TwoSum(new[] { 3, 3 }, 6); // [0, 1]
TwoSum(new[] { -3, 4, 3 }, 0); // [0, 2]
TwoSum(new[] { 1 }, 2); // []
TwoSum(Array.Empty<int>(), 0); // []

06 / Améliorer

Définissez le comportement pour une entrée nulle et le dépassement d'entier. Pour des valeurs int sans restriction, calculez le complément avec long puis vérifiez avant conversion. Documentez la paire renvoyée lorsque plusieurs solutions existent.

07 / Comparer avec l'IA

Faites résoudre le même contrat à un assistant. Vérifiez les doublons, la réutilisation d'indice, le dépassement et les annonces de complexité. Le succès du premier exemple n'est pas une preuve.