Problème

Étant donné un tableau circulaire nums contenant des entiers positifs et négatifs, où à un indice k, un nombre positif signifie un déplacement avant de k positions, et un nombre négatif -k un déplacement arrière de k positions. Le tableau étant circulaire, le dernier élément est suivi du premier, et le premier est précédé du dernier. Il faut déterminer s'il existe une boucle ou un cycle dans nums. Une boucle doit commencer et se terminer au même endice avec une longueur supérieure à 1, et tous les déplacements dans la boucle doivent être dans la même direction (pas de mélange avant et arrière).

Exemples

Entrée : [2,-1,1,2,2]
Sortie : true
Explication : Il existe une boucle aux indices 0 -> 2 -> 3 -> 0. La longueur de la boucle est 3.

Entrée : [-1,2]
Sortie : false
Explication : Le déplacement aux indices 1 -> 1 -> 1 ... ne forme pas une boucle valide car la longueur est 1. Une boucle doit avoir une longueur supérieure à 1.

Entrée : [-2,1,-1,-2,-2]
Sortie : false
Explication : Le déplacement aux indices 1 -> 2 -> 1 -> ... n'est pas une boucle car les déplacements changent de direction (1 -> 2 est avant, 2 -> 1 est arrière). Tous les déplacements dans une boucle doivent être cohérents en direction.

Solution

/**
 * @param {number[]} nums
 * @return {boolean}
 */
function detectCircularArrayLoop(tableau) {
    const longueur = tableau.length;
    const getNextIdx = (pos) => {
        let idxSuivant = (pos + tableau[pos]) % longueur;
        return idxSuivant >= 0 ? idxSuivant : idxSuivant + longueur;
    };
    
    for (let i = 0; i < longueur; i++) {
        if (tableau[i] === 0) continue;
        let ptrLent = i;
        let ptrRapide = getNextIdx(i);
        
        while (tableau[ptrLent] * tableau[ptrRapide] > 0 && 
               tableau[ptrRapide] * tableau[getNextIdx(ptrRapide)] > 0) {
            if (ptrLent === ptrRapide) {
                if (ptrLent === getNextIdx(ptrLent)) break;
                return true;
            }
            ptrLent = getNextIdx(ptrLent);
            ptrRapide = getNextIdx(getNextIdx(ptrRapide));
        }
        
        let posActuelle = i;
        let valInit = tableau[posActuelle];
        while (valInit * tableau[posActuelle] > 0) {
            let prochainePos = getNextIdx(posActuelle);
            tableau[posActuelle] = 0;
            posActuelle = prochainePos;
        }
    }
    return false;
}

Approche

Prenons l'exemple [2,-1,1,2,2] : en partant de l'indice 0 avec la valeur 2, on avance de 2 positions pour atteindre l'indice 2 (valeur 1), puis on avance de 1 position à l'indice 3 (valeur 2), et enfin on avance de 2 positions pour revenir à l'indice 0, formant ainsi une boucle. Le point de départ peut être n'importe quel indice, mais les contraintes imposent une longueur de boucle supérieure à 1 et une direction cohérente.

L'algorithme utilise une technique de pointeurs rapide et lent pour détecter les cycles. Le pointeur lent avance d'un pas (selon la valeur de l'indice actuel) à chaque itération, tandis que le pointeur rapide avance de deux pas. Si une boucle existe, ces pointeurs finiront par se rencontrer. On définit d'abord la longueur du tableau et une fonction getNextIdx pour calculer le prochain indice en tanant compte de la circularité. Ensuite, on parcourt le tableau, en ignorant les éléments nuls (utilisés comme marqueurs pour l'élagage). Pour chaque indice non visité, on initialise les pointeurs lent et rapide. La boucle while vérifie que les valeurs pointées ont le même signe (garantissant une direction uniforme) et que le pointeur rapide et son prochain successeur ont aussi le même signe. Si les pointeurs se rencontrent, on vérifie que la boucle n'est pas de longueur 1 (c'est-à-dire que le pointeur ne pointe pas vers lui-même). Si c'est une boucle valide, on retourne vrai. Sinon, on évolue les pointeurs. Après la détection, on marque tous les indices parcourus à partir du point de départ comme nuls pour éviter les recalculs, optimisant ainsi l'algorithme.