HashSet pra quem sabe o que é uma List no C#

Tanto o HashSet quanto o List são estruturas de dados em C# que permitem armazenar uma coleção de elementos. No entanto, há diferenças importantes entre eles.

O List é uma lista ordenada de elementos, onde cada elemento é acessado por um índice numérico. O List permite elementos duplicados e mantém a ordem dos elementos adicionados.

Por outro lado, o HashSet é uma coleção de elementos não ordenados e não permite elementos duplicados. O HashSet usa um algoritmo de hashing para armazenar e recuperar elementos, o que torna a verificação da presença de um elemento muito rápida em comparação com o List.

Pense na situação em que você precisa encontrar o primeiro número duplicado em um array, onde o índice da segunda ocorrência desse número seja o menor possível. Nesse caso, o uso do HashSet pode ser especialmente útil.

Considere o seguinte exercício: dado um array a que contém apenas números no intervalo de 1 a a.length, devemos encontrar o primeiro número duplicado para o qual a segunda ocorrência tem o índice mínimo. Em outras palavras, se houver mais de um número duplicado, devemos retornar o número cuja segunda ocorrência tem um índice menor do que a segunda ocorrência dos outros números duplicados. Caso não haja elementos que satisfaçam essa condição, o valor retornado será -1.

Imagine que temos o seguinte array:

int[] a = {2, 3, 1, 5, 2, 4, 3};

Nesse caso, o número 2 é o primeiro número duplicado, pois aparece nas posições 0 e 4 do array. A segunda ocorrência do número 2 ocorre na posição 4, que é menor do que a segunda ocorrência dos outros números duplicados (o número 3 aparece nas posições 1 e 6, e o número 5 aparece apenas na posição 3).

Para resolver esse problema, podemos utilizar um HashSet para armazenar os números que encontramos durante a iteração pelo array. Ao percorrer o array, podemos verificar se cada número já existe no HashSet. Se já existir, encontramos o primeiro número duplicado e podemos retorná-lo. Caso contrário, adicionamos o número ao HashSet e continuamos a iteração.

Por isso, no exemplo apresentado, usamos um HashSet para implementar a solução.

int FindFirstDuplicate(int[] array)
{
    HashSet<int> numbers = new HashSet<int>();

    foreach (int num in array)
    {
        if (numbers.Contains(num))
        {
            return num;
        }

        numbers.Add(num);
    }

    return -1;
}

Nesse exemplo, criamos um HashSet chamado numbers para armazenar os números encontrados. Em seguida, percorremos o array utilizando um loop foreach e verificamos se cada número já existe no HashSet. Se já existir, retornamos o número duplicado. Caso contrário, adicionamos o número ao HashSet e continuamos a iteração.

Usar um List exigiria percorrer todo o List para verificar se cada elemento já foi adicionado anteriormente, o que levaria O(n²) tempo no pior caso.

Por outro lado, usar um HashSet permite verificar rapidamente se um elemento já foi adicionado anteriormente, em O(1) tempo no melhor caso. Como o HashSet não permite elementos duplicados, o primeiro elemento duplicado que encontrarmos será a duplicata que procuramos.