Busca Binária (Binary Search)

A busca binária é uma técnica eficiente para localizar um elemento em um array ordenado. O ponto crucial é a definição correta dos limites do intervalo de busca para evitar loops infinitos ou erros de índice.

• Utilize um intervalo bem definido, como [esquerda, direita].
• Certifique-se de atualizar os ponteiros corretamente após comparar o valor central com o alvo (target).

Remoção de Elementos In-place

Para remover elementos de um array sem alocar memória extra, a técnica de dois ponteiros (puntero rápido e puntero lento) é a mais indicada. O ponteiro rápido percorre todos os elementos, enquanto o lento marca a posição onde o próximo elemento válido deve ser inserido.

Quando o valor apontado pelo ponteiro rápido não é o elemento a ser removido, ele é copiado para a posição do ponteiro lento, e este é incrementado.

Quadrados de um Array Ordenado

Dado um array ordenado que pode conter números negativos, o desafio é retornar um novo array com os quadrados também ordenados. Como os maiores valores quadrados estarão nas extremidades (devido aos valores negativos elevados ao quadrado), utiliza-se dois pnoteiros: um no início e outro no fim do array.

Comparamos os quadrados de ambos os lados e preenchemos o array de destino do final para o início.

Sub-array de Comprimento Mínimo (Janela Deslizante)

Para encontrar o menor sub-array cuja soma seja maior ou igual a um valor alvo, a técnica de Janela Deslizante (Sliding Window) reduz a complexidade temporal de O(n²) para O(n). Expandimos a janela movendo o ponteiro da direita e a contraímos movendo o ponteiro da esquerda sempre que a condição da soma for atingida.

class Solution {
public:
    int minSubArrayLen(int alvo, vector<int>& numeros) {
        int resultado = INT_MAX;
        int somaAtual = 0;
        int inicioJanela = 0;

        for (int fimJanela = 0; fimJanela < numeros.size(); fimJanela++) {
            somaAtual += numeros[fimJanela];
            
            while (somaAtual >= alvo) {
                int larguraJanela = fimJanela - inicioJanela + 1;
                resultado = min(resultado, larguraJanela);
                
                somaAtual -= numeros[inicioJanela];
                inicioJanela++;
            }
        }

        return (resultado == INT_MAX) ? 0 : resultado;
    }
};

Geração de Matriz Espiral II

A construção de uma matriz em espiral exige uma simulação rigorosa do movimento em quatro direções: dirieta, baixo, esquerda e cima. A chave para o sucesso é manter a consistência no tratamento das bordas (por exemplo, sempre fechar o intervalo no formato [aberto, fechado)).

• O número de camadas (ou voltas) a serem processadas é n / 2.
• Se n for ímpar, o elemento central deve ser preenchido manualmente ao final.

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> matriz(n, vector<int>(n, 0));
        int startX = 0, startY = 0;
        int offset = 1;
        int valor = 1;
        int camadas = n / 2;

        while (camadas--) {
            int i = startX;
            int j = startY;

            // Percorre topo da esquerda para a direita
            for (j = startY; j < n - offset; j++) {
                matriz[startX][j] = valor++;
            }
            // Percorre lateral direita de cima para baixo
            for (i = startX; i < n - offset; i++) {
                matriz[i][j] = valor++;
            }
            // Percorre base da direita para a esquerda
            for (; j > startY; j--) {
                matriz[i][j] = valor++;
            }
            // Percorre lateral esquerda de baixo para cima
            for (; i > startX; i--) {
                matriz[i][j] = valor++;
            }

            startX++;
            startY++;
            offset++;
        }

        if (n % 2 != 0) {
            matriz[n / 2][n / 2] = valor;
        }

        return matriz;
    }
};

Cálculo de Soma de Intervalos (Soma de Prefixos)

Para consultar a soma de elementos entre dois índices [i, j] repetidas vezes, a abordagem de força bruta é ineficiente. A técnica de Soma de Prefixos (Prefix Sum) pré-calcula uma estrutura onde cada posição k armazena a soma de todos os elementos de 0 até k.

Com essa estrutura, a soma de qualquer intervalo pode ser obtida em tempo constante O(1) através da subtração: soma[j] - soma[i-1].