# Two Pointers

### Introdução

Two Pointers é uma técnica muito utilizada em questões de leetcode envolvendo estruturas de dados iteráveis. Como o próprio nome sugere, consiste de utilizar 2, ou mais, ponteiros para percorrer a estrutura.&#x20;

Através dessa técnica, podemos criar algoritmos mais eficientes, escapando muitas vezes de uma time complexity de O(N^2).

### Prefix Sum

O principal objetivo da técnica Prefix Sum é permitir você fazer queries de soma em tempo constante.&#x20;

Por exemplo, imagine o array \[0, 1, 2, 3, 4, 5] e eu peço a você para fazer um algoritmo que some todos os elementos desse array.&#x20;

Você poderia iterar o array, e fazer a soma, resultando em 15, e isso te custaria um tempo de execução O (N). &#x20;

Imagine, agora, que você precisa saber a soma até o índice 2 do array, do índice 2 até o índice 4, e a soma de todos os elementos do array. Você teria 3 operações O (N). Fica nítido que se você precisa fazer muitas operações de _queries de soma_ você acaba consumindo muito processamento, então o que vamos fazer, é uma troca.&#x20;

Vamos criar um array que consiste em todas as somas do índice 0 até o índice i, nesse caso:

\[0, 1, 3, 6, 10, 15]&#x20;

Então, se eu quiser saber a soma de todos os elementos até o índice 2, basta eu acessar o índice 2 do array. É claro que criar esse array custa O (N) tanto no tempo de execução, quanto na memória. Mas acessar as somas depois é O (1), reduzindo demasiadamente o tempo de execução de fazer muitas operações. Ou seja, nós fizemos uma troca, trocamos uma parte da memória para termos um algoritmo mais rápido!&#x20;

