Este artigo aborda três problemas comuns em algoritmos de arrays: calcular os quadrados de elementos em um array ordenado, encontrar o subarray de soma mínima e gerar uma matriz em espiral.

Quadrados de um Array Ordenado (977. Squares of a Sorted Array)

O objetivo é receber um array de inteiros em ordem não decrescente, calcular o quadrado de cada elemento e, em seguida, retornar um novo array com os quadrados também em ordem não decrescente. Uma abordagem eficiente utiliza a técnica de dois ponteiros.

Inicializamos dois ponteiros, um no início (esquerda) e outro no final (direita) do array de entrada. Um ponteiro auxiliar (posicao) é usado para preencher o array de resultado a partir do final. Comparamos os quadrados dos elementos apontados por esquerda e direita. O maior quadrado é colocado na posição atual de posicao no array de resultado, e o ponteiro correspondente (esquerda ou direita) é movido, enquanto posicao é decrementado.

#include <vector>
#include <cmath>
#include <algorithm>

class Solution {
public:
    std::vector<int> sortedSquares(std::vector<int>& nums) {
        int esquerda = 0;
        int direita = nums.size() - 1;
        int posicao = direita;
        std::vector<int> resultado(nums.size());

        while (esquerda <= direita) {
            int quadradoEsquerda = nums[esquerda] * nums[esquerda];
            int quadradoDireita = nums[direita] * nums[direita];

            if (quadradoEsquerda > quadradoDireita) {
                resultado[posicao] = quadradoEsquerda;
                esquerda++;
            } else {
                resultado[posicao] = quadradoDireita;
                direita--;
            }
            posicao--;
        }
        return resultado;
    }
};
</int></int></int></algorithm></cmath></vector>

Subarray de Soma Mínima (209. Minimum Size Subarray Sum)

Este problema busca o menor subarray contínuo de um array de inteiros positivos cuja soma seja maior ou igual a um determinado target. A abordagem mais eficaz é a da "janela deslizante".

Utilizamos dois ponteiros, inicioJanela e fimJanela, para definir a janela deslizante. O ponteiro fimJanela avança, adicionando elementos à soma atual (somaAtual). Se somaAtual atingir ou exceder o target, registramos o comprimento da janela atual (fimJanela - inicioJanela + 1) e tentamos encolher a janela pelo lado esquerdo, subtraindo o elemento em inicioJanela e incrementando inicioJanela, até que somaAtual seja menor que target novamente. O menor comprimento registrado é a resposta.

#include <vector>
#include <limits>
#include <algorithm>

class Solution {
public:
    int minSubArrayLen(int target, std::vector<int>& nums) {
        int inicioJanela = 0;
        int fimJanela = 0;
        long long somaAtual = 0; // Usar long long para evitar overflow
        int comprimentoMinimo = std::numeric_limits<int>::max();

        while (fimJanela < nums.size()) {
            somaAtual += nums[fimJanela];

            while (somaAtual >= target) {
                comprimentoMinimo = std::min(comprimentoMinimo, fimJanela - inicioJanela + 1);
                somaAtual -= nums[inicioJanela];
                inicioJanela++;
            }
            fimJanela++;
        }

        return (comprimentoMinimo == std::numeric_limits<int>::max()) ? 0 : comprimentoMinimo;
    }
};
</int></int></int></algorithm></limits></vector>

Matriz Espiral II (59. Spiral Matrix II)

O desafio aqui é preencher uma matriz quadrada n x n com inteiros de 1 a n*n em um padrão espiral, começando do canto superior esquerdo e movendo-se no sentido horário.

A lógica central é simular o preenchimento da matriz em camadas concêntricas. Definimos limites para as bordas da camada atual (linhaInicio, linhaFim, colunaInicio, colunaFim). Iteramos preenchendo a borda superior, depois a direita, a inferior e, por fim, a esquerda. Após completar uma camada, ajustamos os limites para a próxima camada interna e repetimos o processo. Um contador (valorAtual) rastreia o próximo número a ser inserido na matriz.

#include <vector>

class Solution {
public:
    std::vector<:vector>> generateMatrix(int n) {
        std::vector<:vector>> matriz(n, std::vector<int>(n));
        int valorAtual = 1;
        int linhaInicio = 0, linhaFim = n - 1;
        int colunaInicio = 0, colunaFim = n - 1;

        while (linhaInicio <= linhaFim && colunaInicio <= colunaFim) {
            // Preencher linha superior
            for (int j = colunaInicio; j <= colunaFim; ++j) {
                matriz[linhaInicio][j] = valorAtual++;
            }
            linhaInicio++;

            // Preencher coluna direita
            for (int i = linhaInicio; i <= linhaFim; ++i) {
                matriz[i][colunaFim] = valorAtual++;
            }
            colunaFim--;

            // Preencher linha inferior (se ainda houver linha)
            if (linhaInicio <= linhaFim) {
                for (int j = colunaFim; j >= colunaInicio; --j) {
                    matriz[linhaFim][j] = valorAtual++;
                }
                linhaFim--;
            }

            // Preencher coluna esquerda (se ainda houver coluna)
            if (colunaInicio <= colunaFim) {
                for (int i = linhaFim; i >= linhaInicio; --i) {
                    matriz[i][colunaInicio] = valorAtual++;
                }
                colunaInicio++;
            }
        }
        return matriz;
    }
};
</int></:vector></:vector></vector>

Estes exemplos demonstram a aplicação de técnicas fundamentais em manipulação de arrays, como ponteiros duplos e janelas deslizantes, para resolver problemas de forma eficiente.