LeetCode – Encuentra el número duplicado (Java)

Dada una matriz que contiene n + 1 enteros donde cada entero está entre 1 y n (inclusive), demuestre que debe existir al menos un número duplicado. Suponga que solo hay un número duplicado, encuentre el duplicado.

Nota:
1) No debe modificar la matriz (suponga que la matriz es de solo lectura).
2) Debe usar solo espacio adicional constante, O (1).
3) La complejidad del tiempo de ejecución debe ser menor que O (n ^ 2).
4) Solo hay un número duplicado en la matriz, pero podría repetirse más de una vez.

Solución Java: ciclo de búsqueda

A continuación se muestra cómo funciona la solución de punteros rápidos y lentos. Básicamente contiene 2 pasos: 1) encontrar el punto de encuentro 2) empezar desde el principio y el punto de encuentro respectivamente y encontrar el punto de intersección.

public int findDuplicate(int[] nums) {
    int slow = 0;
    int fast = 0;
 
    do{
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while(slow != fast);
 
    int find = 0;
 
    while(find != slow){
        slow = nums[slow];
        find = nums[find];
    }
    return find;
}

Si podemos asumir que solo hay un número duplicado, se puede resolver fácilmente usando la suma de la matriz.

public int findDuplicate(int[] nums) {
    int sum = 0;
    for(int i: nums){
        sum+=i;
    }
 
    int n=nums.length;
    return sum - ((n-1)*n)/2;
}