Enunciado

Dado um array nums de n inteiros positivos e um inteiro positivo target, determine o comprimento do menor subarray contínuo cuja soma seja maior ou igual a target. Caso não exista subarray que satisfaça a condição, retorne 0.

Exemplo

Entrada: target = 7, nums = [2, 3, 1, 2, 4, 3]
Saída: 2
Explicação: O subarray [4, 3] atinge a soma 7 e é o menor possível.

Solução ingênua — O(n²)

A abordagem mais simples gera todos os subarrays contínuos. Um laço externo define o índice inicial, enquanto um laço interno estende o índice final e acumula a soma. Sempre que a soma atinge ou ultrapassa o valor alvo, o comprimento do subarray é comparado ao menor já registrado.

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int menor = Integer.MAX_VALUE;
        
        for (int inicio = 0; inicio < n; inicio++) {
            int soma = 0;
            for (int fim = inicio; fim < n; fim++) {
                soma += nums[fim];
                if (soma >= target) {
                    menor = Math.min(menor, fim - inicio + 1);
                    break;
                }
            }
        }
        
        return menor == Integer.MAX_VALUE ? 0 : menor;
    }
}

Essa implementação é fácil de entender, mas testa todas as combinações e, no pior caso, realiza um número quadrático de operações, podendo ultrapassar o limite de tempo para entradas grandes.

Janela deslizante — O(n)

Como todos os elementos são positivos, a soma da janela cresce à medida que expandimos a direita e diminui quando contraímos a esquerda. Esse invariante permite resolver o problema com uma única passagem e dois ponteiros.

A janela é delimitada pelos índices esquerda e direita. O ponteiro direito avança a cada iteração, adicionando o elemento à soma. Assim que a soma atinge ou supera o alvo, contraímos a janela pelo lado esquerdo, atualizando o menor comprimento encontrado, até que a soma fique abaixo do alvo novamente.

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int tamanhoMinimo = Integer.MAX_VALUE;
        int esquerda = 0;
        int soma = 0;
        
        for (int direita = 0; direita < nums.length; direita++) {
            soma += nums[direita];
            
            while (soma >= target) {
                tamanhoMinimo = Math.min(tamanhoMinimo, direita - esquerda + 1);
                soma -= nums[esquerda];
                esquerda++;
            }
        }
        
        return tamanhoMinimo == Integer.MAX_VALUE ? 0 : tamanhoMinimo;
    }
}

Princípios da técnica

• Conteúdo da janela: o subarray contínuo cuja soma é maior ou igual a target.
• Movimento da esquerda: enquanto a soma atual for suficiente, remova o elemento mais à esquerda e tente obter uma janela menor.
• Movimento da direita: expanda a janela incluindo o próximo elemento do array.

Complexidade

Cada índice é visitado no máximo duas vezes: uma vez pelo ponteiro direito e outra pelo ponteiro esquerdo. Portanto, a complexidade temporal é O(n) e a espacial é O(1).