BlackTDN :: LeetCode :: Implementando o Algoritmo Two Sum em (x)Base/TLPP

_Créditos das imagens: ChatGPT_

# Implementando o Algoritmo Two Sum em (x)Base/TLPP

O problema [**Two Sum**](https://leetcode.com/problems/two-sum/) é um desafio clássico de algoritmos, que consiste em encontrar dois números em um array que, somados, resultem em um valor-alvo específico. Neste artigo, vamos explorar a implementação deste algoritmo na linguagem de programação (x)Base/TLPP, utilizando tabelas hash para uma computação eficiente.

---

## Enunciado do Problema

Dado um array de inteiros e um valor-alvo, identifique os índices dos dois números no array cuja soma seja igual ao alvo. Cada entrada terá exatamente uma solução, e o mesmo elemento não pode ser usado duas vezes. Os índices podem ser retornados em qualquer ordem.

---

### Exemplo:

```plaintext
Entrada: nums = [2, 7, 11, 15], target = 9  
Saída: [0, 1]  
Explicação: nums[0] + nums[1] = 2 + 7 = 9
```

---

## Implementação em (x)Base/TLPP

A solução utiliza uma tabela hash para armazenar cada número no array junto com seu índice. À medida que percorremos o array, calculamos o complemento (ou seja, `alvo - número atual`) e verificamos se este complemento existe na tabela hash. Se existir, encontramos os dois números cuja soma é igual ao alvo.

Aqui está o código em (x)Base/TLPP que implementa essa abordagem:

```(x)Base/TLPP
/* 
    Algoritmo Two Sum em (x)Base/TLPP
    Resolve o problema de encontrar dois números em um array cuja soma seja igual ao valor-alvo.
    Liberado para domínio público.
*/

procedure Main()
    local aNums as array
    local aResult as array
    local nTarget as numeric
    local lZeroBasedIndex as logical := .F.

    aNums := {2, 7, 11, 15}
    nTarget := 9
    aResult := TwoSum(aNums, nTarget, lZeroBasedIndex)
    ? "Índices: ", hb_JSONEncode(aResult), if(lZeroBasedIndex, "Usando índice baseado em zero", "Usando índice baseado em um")
    ? "  "

return

static function TwoSum(aNums as array, nTarget as numeric, lZeroBasedIndex as logical)
    local hSeen as hash := hb_HASH()
    local i, nAT, nNum, nComplement as numeric

    hb_default(@lZeroBasedIndex, .F.)

    for i := 1 to Len(aNums)
        nNum := aNums[i]
        nComplement := nTarget - nNum

        if (nAT := hb_hPos(hSeen, nComplement)) > 0
            return { hb_hValueAt(hSeen, nAT), i - (if(lZeroBasedIndex, 1, 0)) }
        endif

        hb_hSet(hSeen, nNum, i - (if(lZeroBasedIndex, 1, 0)))
    next i

    return {}
```

---

## Explicação do Código

1. **Procedimento Principal**:  
   O array `aNums` e o valor-alvo `nTarget` são inicializados. O procedimento chama a função `TwoSum`, que retorna os índices dos dois números que somam o valor-alvo. O resultado é exibido em formato JSON.  

2. **Função TwoSum**:  
   - Uma tabela hash `hSeen` é inicializada para armazenar cada número e seu índice.  
   - Para cada número `nNum` no array, calculamos seu complemento em relação ao alvo (`nComplement = nTarget - nNum`).  
   - Verificamos se `nComplement` já está em `hSeen`. Se sim, retornamos os índices de `nNum` e `nComplement`.  
   - Se o complemento não for encontrado, adicionamos o número atual e seu índice à tabela `hSeen`.  
   - Caso nenhuma solução seja encontrada (o que não ocorre neste problema), a função retorna um array vazio.  

---

## Eficiência

A solução tem complexidade de tempo **O(n)**, onde **n** é o número de elementos no array. Isso ocorre porque as operações de inserção e busca em tabelas hash têm, em média, complexidade constante.

---

## Conclusão

Implementar o algoritmo Two Sum em (x)Base/TLPP mostra como a linguagem pode lidar eficientemente com desafios algorítmicos clássicos. O uso de tabelas hash possibilita uma solução otimizada, tornando esta abordagem prática e elegante.

Para acessar o código completo e exemplos adicionais, visite o [repositório no GitHub](https://github.com/naldodj/naldodj-xbase-leetcode-solutions).

---

## Hashtags  

#(x)BaseTLPPProgramming #AlgoritmoTwoSum #TabelaHash #DesafiosDeCódigo #ProgramaçãoEficiente #TutorialDeCódigo #BlogDeTecnologia #OtimizaçãoDeCódigo #DesenvolvimentoDeSoftware #LeetCodeSolutions  

---