Recherche de Deux Nombres par Somme Cible

Étant donné un tableau d'entiers et une valeur cible, identifier les indices de deux nombres dont la somme équivaut à la cible. Chaque élément ne peut être utilisé qu'une fois.

Exemple :

nums = [2, 7, 11, 15], target = 9 → Résultat : [0, 1]

public int[] trouverPaire(int[] nombres, int cible) {
    int[] indicesResultats = new int[2];
    if (nombres == null || nombres.length == 0) return indicesResultats;
    
    Map<Integer, Integer> dictionnaire = new HashMap<>();
    for (int idx = 0; idx < nombres.length; idx++) {
        int complement = cible - nombres[idx];
        if (dictionnaire.containsKey(complement)) {
            indicesResultats[0] = dictionnaire.get(complement);
            indicesResultats[1] = idx;
            break;
        }
        dictionnaire.put(nombres[idx], idx);
    }
    return indicesResultats;
}

Initialise un tableau résultat et vérifie les entrées invalides. Utilise une HashMap pour stocker les nombres parcourus et leurs indices. Pour chaque élément, calcule son complément et vérifie sa présence dans la map.

Comptage de Quadruplets à Somme Nulle

Calculer le nombre de quadruplets (i, j, k, l) tels que A[i] + B[j] + C[k] + D[l] = 0. Tous les tableaux ont la même longueur.

Exemple :

A = [1, 2], B = [-2, -1], C = [-1, 2], D = [0, 2] → Résultat : 2

public int compterQuadruplets(int[] tableauA, int[] tableauB, int[] tableauC, int[] tableauD) {
    int compteur = 0;
    Map<Integer, Integer> sommesAB = new HashMap<>();
    
    for (int a : tableauA) {
        for (int b : tableauB) {
            int somme = a + b;
            sommesAB.put(somme, sommesAB.getOrDefault(somme, 0) + 1);
        }
    }
    
    for (int c : tableauC) {
        for (int d : tableauD) {
            compteur += sommesAB.getOrDefault(-(c + d), 0);
        }
    }
    return compteur;
}

Stocke les sommes des deux premiesr tableaux dans une HashMap avec leurs occurrences. Parcourt ensuite les deux derniers tableaux et incrémente le compteur pour chaque somme opposée trouvée.

Recherche de Triplets à Somme Nulle

Trouver tous les triplets uniques dans un tableau dont la somme est nulle.

Exemple :

nums = [-1, 0, 1, 2, -1, -4] → Résultat : [[-1, -1, 2], [-1, 0, 1]]

public List<List<Integer>> trouverTriplets(int[] nombres) {
    List<List<Integer>> resultats = new ArrayList<>();
    Arrays.sort(nombres);
    
    for (int i = 0; i < nombres.length; i++) {
        if (nombres[i] > 0) break;
        if (i > 0 && nombres[i] == nombres[i - 1]) continue;
        
        int gauche = i + 1, droite = nombres.length - 1;
        while (gauche < droite) {
            int somme = nombres[i] + nombres[gauche] + nombres[droite];
            if (somme < 0) gauche++;
            else if (somme > 0) droite--;
            else {
                resultats.add(Arrays.asList(nombres[i], nombres[gauche], nombres[droite]));
                while (gauche < droite && nombres[gauche] == nombres[gauche + 1]) gauche++;
                while (gauche < droite && nombres[droite] == nombres[droite - 1]) droite--;
                gauche++;
                droite--;
            }
        }
    }
    return resultats;
}

Trie le tableau et utilise une approche à deux pointeurs. Évite les doublons en sautant les éléments identiques consécutifs. Ajuste les pointeurs en fonction de la somme partielle.

Recherche de Quadruplets par Somme Cible

Trouver tous les quadruplets uniques dans un tableau dont la somme équivaut à une cible spécifique.

Exemple :

nums = [1, 0, -1, 0, -2, 2], target = 0 → Résultat : [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

public List<List<Integer>> trouverQuadruplets(int[] nombres, int cible) {
    List<List<Integer>> resultats = new ArrayList<>();
    Arrays.sort(nombres);
    
    for (int i = 0; i < nombres.length; i++) {
        if (i > 0 && nombres[i] == nombres[i - 1]) continue;
        
        for (int j = i + 1; j < nombres.length; j++) {
            if (j > i + 1 && nombres[j] == nombres[j - 1]) continue;
                
            int gauche = j + 1, droite = nombres.length - 1;
            while (gauche < droite) {
                long somme = (long) nombres[i] + nombres[j] + nombres[gauche] + nombres[droite];
                if (somme < cible) gauche++;
                else if (somme > cible) droite--;
                else {
                    resultats.add(Arrays.asList(nombres[i], nombres[j], nombres[gauche], nombres[droite]));
                    while (gauche < droite && nombres[gauche] == nombres[gauche + 1]) gauche++;
                    while (gauche < droite && nombres[droite] == nombres[droite - 1]) droite--;
                    gauche++;
                    droite--;
                }
            }
        }
    }
    return resultats;
}

Étend l'approche des triplets avec une boucle supplémentarie. Utilise un type long pour éviter les dépassements d'entier. Applique le même mécanisme de déduplication et d'ajustement des pointeurs.