Dado um array de inteiros nums de tamanho n, onde todos os elementos estão no intervalo \[1, n\] e cada número aparece uma ou duas vezes, o objetivo é encontrar todos os números que aparecem duas vezes e retorná-los em um array. A solução deve ter complexidade de tempo O(n) e utilizar apenas espaço constante adicional.

Uma abordagem eficaz para resolver este problema sem usar espaço extra significativo é aproveitar o fato de que os números no array estão dentro de um intervalo específico que se correlaciona com os índices do array. Podemos usar o próprio array como uma tabela de hash, modificando os valores para indicar a ocorrência de um número.

Abordagem 1: Modificação de Valores e Verificação de Limite

Esta técnica consiste em iterar pelo array e, para cada número, calcular seu índice "correto" no array. O índice correto para um número num é (num - 1) % n, pois os números estão entre 1 e n, e os índices do array vão de 0 a n-1. Em seguida, adicionamos n ao valor no índice calculado. Isso serve como um marcador. Se, após essa etapa, um valor em um índice for maior que 2 \* n, significa que o número correspondente a esse índice apareceu mais de uma vez. Por quê? Porque o valor original era no máximo n, e adicionamos n a ele em sua primeira ocorrência. Se ele ocorrer novamente, adicionaremos n mais uma vez, tornando o valor original + 2n ou mais.

O código a seguir implementa essa lógica:

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<integer> findDuplicates(int[] nums) {
        int n = nums.length;
        // Primeira passagem: marcar a ocorrência dos números
        for (int num : nums) {
            // Calcula o índice correspondente ao número, considerando que os números são de 1 a n
            // e os índices são de 0 a n-1. O módulo n garante que permaneçamos dentro dos limites
            // caso o valor já tenha sido modificado (adicionando n).
            int index = (num - 1) % n;
            // Adiciona n ao valor no índice correspondente. Isso marca que o número 'index + 1' foi visto.
            nums[index] += n;
        }

        List<integer> duplicateNumbers = new ArrayList<>();
        // Segunda passagem: identificar os números duplicados
        for (int i = 0; i < n; i++) {
            // Se o valor no índice 'i' for maior que 2*n, significa que o número 'i+1'
            // foi visto pelo menos duas vezes.
            if (nums[i] > 2 * n) {
                duplicateNumbers.add(i + 1);
            }
        }
        return duplicateNumbers;
    }
}
</integer></integer>

Abordagem 2: Colocando Elementos em Suas Posições Corretas

Outra maneira de resolver isso é tentar posicionar cada número x no índice x-1. Como os números estão no intervalo \[1, n\], se um número x aparece duas vezes, então seu par correspondente estará em uma posição j onde o número j+1 não está presente no array. Iteramos pelo array e, para cada elemento nums\[i\], o trocamos com o elemento na posição nums\[i\]-1 até que nums\[i\] esteja em sua posição correta (ou seja, nums\[i\] == i + 1) ou até que nums\[i\] seja igual ao elemento que deveria estar em sua posição de destino (nums\[i\] == nums\[nums\[i\]-1\]). Após organizar os elementos, uma segunda passagem identifica os números duplicados: se nums\[i\] != i + 1, então nums\[i\] é um duplicado.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<integer> findDuplicates(int[] nums) {
        int n = nums.length;
        // Primeira passagem: organizar os números em suas posições corretas
        for (int i = 0; i < n; ++i) {
            // Enquanto o número atual não estiver em sua posição correta E
            // o número atual não for igual ao número que deveria estar em sua posição de destino
            // (isso evita loops infinitos quando há duplicados)
            while (nums[i] != nums[nums[i] - 1]) {
                swap(nums, i, nums[i] - 1);
            }
        }

        List<integer> duplicateNumbers = new ArrayList<>();
        // Segunda passagem: encontrar os números que não estão em suas posições corretas
        for (int i = 0; i < n; ++i) {
            // Se o número no índice 'i' não for 'i+1', então ele é um duplicado
            if (nums[i] != i + 1) {
                duplicateNumbers.add(nums[i]);
            }
        }
        return duplicateNumbers;
    }

    // Função auxiliar para troca de elementos
    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}
</integer></integer>

Abordagem 3: Uso de Sinal Negativo como Marcador

Podemos usar o sinal do número em um determinado índice para indicar se o número correspondente a esse índice já foi visto. Iteramos pelo array. Para cada número nums\[i\], pegamos seu valor absoluto x. Em seguida, verificamos o sinal de nums\[x-1\]. Se nums\[x-1\] for positivo, significa que o número x ainda não foi encontrado, então o tornamos negativo (nums\[x-1\] = -nums\[x-1\]). Se nums\[x-1\] for negativo, significa que o número x já foi encontrado antes, então adicionamos x à lista de duplicados.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<integer> findDuplicates(int[] nums) {
        int n = nums.length;
        List<integer> duplicateNumbers = new ArrayList<>();

        // Iteramos pelo array
        for (int i = 0; i < n; ++i) {
            // Pegamos o valor absoluto do número atual, pois ele pode já ter sido negativado
            int currentValue = Math.abs(nums[i]);
            // Calculamos o índice correspondente a este valor (valor - 1)
            int indexToMark = currentValue - 1;

            // Se o número no índice a ser marcado já for negativo, significa que já vimos este número antes
            if (nums[indexToMark] < 0) {
                // Adicionamos o valor absoluto (o número duplicado) à lista de resultados
                duplicateNumbers.add(currentValue);
            } else {
                // Caso contrário, marcamos este número como visto, negativando o valor no índice correspondente
                nums[indexToMark] = -nums[indexToMark];
            }
        }
        // Não é necessário uma segunda passagem, pois os duplicados são adicionados durante a primeira
        return duplicateNumbers;
    }
}
</integer></integer>

Todas essas abordagenns alcançam a complexidade de tempo O(n) e utilizam espaço constante adicional, modificando o array de entrada para armazenar inforrmações sobre as ocorrências dos números.