A identificação de elementos repetidos em coleções de dados é um problema fundamental em ciência da computação, frequentemente encontrado em desafios de algoritmos como os do LeetCode. Veremos a seguir diferentes estratégias para resolver duas variações desse problema: a detecção simples de duplicatas e a busca por duplicatas dentro de um intervalo específico k.

Problema 1: Verificação de Existência de Duplicatas

O objetivo é determinar se qualquer valor aparece ao menos duas vezes em um array de inteiros. A função deve retornar true se houver duplicatas e false caso todos os elementos sejam distintos.

Abordagem 1: Ordenação de Vetores

Ao ordenar o array, todos os elementos iguais ficam adjacentes. Isso permite identificar duplicatas com uma única passagem após a ordenação. A complexidade de tempo é definida pelo algoritmo de sort, sendo O(n log n).

class Solution {
public:
    bool containsDuplicate(vector<int>& lista) {
        if (lista.size() <= 1) return false;
        
        // Ordenação in-place
        std::sort(lista.begin(), lista.end());
        
        for (size_t i = 0; i < lista.size() - 1; ++i) {
            if (lista[i] == lista[i + 1]) {
                return true;
            }
        }
        return false;
    }
};

Abordagem 2: Utilizando Tabelas de Hash (Unordered Set)

Esta abordagem utiliza uma estrutura de dados de conjunto (hash set) para armazenar elementos já visitados. A busca em um unordered_set tem tempo médio constante, resultando em uma complexidade O(n).

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> elementosVistos;
        
        for (const int& valor : nums) {
            // Se o elemento já existe no set, encontramos uma duplicata
            if (elementosVistos.find(valor) != elementosVistos.end()) {
                return true;
            }
            elementosVistos.insert(valor);
        }
        return false;
    }
};

Problema 2: Duplicatas em Intervalo Limitado (K)

Nesta variação, precisamos encontrar dois índices distintos i e j tais que nums[i] == nums[j] e a diferença absoluta entre os índices seja, no máximo, k.

Abordagem 1: Janela Deslizante com Hash Set

Podemos manter um conjunto contendo apenas os elementos que estão dentro da janela de distância k. Conforme avançamos no array, removemos o elemento que saiu do alcance da janela e verificamos se o novo elemento já existe no conjunto atual.

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& arr, int k) {
        unordered_set<int> janela;
        
        for (int i = 0; i < arr.size(); ++i) {
            // Mantém o tamanho da janela removendo elementos fora do alcance k
            if (i > k) {
                janela.erase(arr[i - k - 1]);
            }
            
            // Tenta inserir; se já existir, insert().second será false
            if (!janela.insert(arr[i]).second) {
                return true;
            }
        }
        return false;
    }
};

Abordagem 2: Mapeamento de Último Índice

Outra estratégia eficiente utiliza um unordered_map para armazenar o valor do elemento como chave e seu índice mais recente como valor. Ao encontrar um número que já está no mapa, calculamos a distância entre o índice atual e o anterior.

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> mapaIndices;
        
        for (int i = 0; i < nums.size(); ++i) {
            int numAtual = nums[i];
            
            if (mapaIndices.count(numAtual)) {
                if (i - mapaIndices[numAtual] <= k) {
                    return true;
                }
            }
            // Atualiza ou insere o índice atual do número
            mapaIndices[numAtual] = i;
        }
        return false;
    }
};

Considerações sobre Performance

Para o primeiro problema, a solução com unordered_set é geralmente mais rápida devido à complexidade linear, embora consuma mais memória que a ordenação. No segundo problema, a técnica de janela deslizante otimiza o uso de memória, mantendo no máximo k elementos no conjunto, o que é ideal quando k é significativamente menor que o tamanho total do array.