Introdução
Bem-vindos a mais uma publicação no blog A Arte de Programar! Hoje, vamos falar sobre o desafio: 2824. Count Pairs Whose Sum is Less than Target disponível no LeetCode.
Se você acompanha nosso blog, provavelmente já está familiarizado com a técnica dos dois ponteiros, que abordamos em posts anteriores. Ela é uma estratégia fundamental para resolver problemas de arrays e strings com elegância e eficiência. Neste artigo, não apenas abordaremos o problema “2824. Count Pairs Whose Sum is Less than Target” utilizando essa técnica, mas também aprofundaremos nosso entendimento de suas mecânicas e aplicações.
Vamos discutir o problema, explorar soluções em Java e Python, e analisar as complexidades envolvidas.
Vamos começar!
Entendendo o Problema 2824. Count Pairs Whose Sum is Less than Target
O problema “2824. Count Pairs Whose Sum is Less than Target” é um desafio comum em entrevistas de programação e é assim: Dado um array de inteiros e um valor-alvo, conte o número de pares no array cuja soma é menor que o valor-alvo.
À primeira vista, isso pode parecer simples – basta verificar todos os pares possíveis e contar aqueles que se encaixam nos critérios, certo? No entanto, essa abordagem de força bruta pode ser ineficiente, especialmente com arrays maiores. Considerando este cenário é que a técnica dos dois ponteiros entra em jogo, oferecendo uma solução mais otimizada.
A técnica dos dois ponteiros é um método elegante que utiliza dois ponteiros para percorrer o array. Neste caso, usamos essa técnica para encontrar e contar pares de forma eficiente. A beleza deste método reside em sua simplicidade e eficiência, reduzindo significativamente a complexidade de tempo em comparação com a abordagem de força bruta.
Como esta técnica funciona exatamente para este problema?
Exploraremos isso em detalhes com nossas soluções em Java e Python nas seções seguintes. Mas, em essência, ao ordenar o array e mover dois ponteiros de extremidades opostas, podemos identificar e contar rapidamente os pares que atendem à nossa condição – sua soma sendo menor que o alvo.
Explorando o Algoritmo: A Técnica dos Dois Ponteiros em Ação
Após mergulharmos nas complexidades do Problema 2824. Count Pairs Whose Sum is Less than Target e na técnica dos dois ponteiros, estamos agora prontos para traduzir nosso entendimento em código.
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class CountPairs {
public static int countPairs(List<Integer> nums, int target) {
Collections.sort(nums); // Ordenando o array
int result = 0;
int left = 0;
int right = nums.size() - 1;
while (left < right) {
if (nums.get(left) + nums.get(right) < target) {
result += right - left; // Contando os pares
left++; // Movendo o ponteiro esquerdo para frente
} else {
right--; // Movendo o ponteiro direito para trás
}
}
return result;
}
public static void main(String[] args) {
List<Integer> nums = Arrays.asList(-6, 2, 5, -2, -7, -1, 3);
System.out.println(countPairs(nums, -2));
}
}
def countPairs(nums, target):
nums.sort() # Ordenando o array
left, right = 0, len(nums) - 1
count = 0
while left < right:
if nums[left] + nums[right] < target:
count += right - left
left += 1
else:
right -= 1
return count
A técnica dos dois ponteiros é um método poderoso no design de algoritmos, particularmente útil para resolver problemas envolvendo arrays. No contexto do Problema “2824. Count Pairs Whose Sum is Less than Target”, esta técnica nos permite contar de forma eficiente o número de pares cuja soma é menor que o valor alvo.
Veja como o algoritmo funciona:
Ordenar o Array: Começamos ordenando o array em ordem ascendente. A ordenação é crucial porque organiza os elementos de forma que possamos explorar sua ordem para otimizar a contagem dos pares.
Inicializar Ponteiros: Usamos dois ponteiros, left e right, que inicialmente apontam para o primeiro (índice 0) e o último elemento (size - 1) do array, respectivamente.
Iterar e Avaliar: Iteramos pelo array usando esses ponteiros com a seguinte lógica:
- Se a soma dos elementos nos ponteiros
lefte right for menor que o alvo, passamos para a próxima etapa de contagem de pares válidos (explicado mais adiante). - Se a soma for igual ou maior que o alvo, movemos o ponteiro right um passo para a esquerda (decrementando right), pois precisamos de uma soma menor.
Contando os Pares: Quando descobrimos que a soma de nums[left] + nums[right] é menor que o alvo, significa que não apenas este par específico atende à condição, mas também todos os pares formados entre left e cada elemento de left até right - 1 (inclusivo) satisfarão a condição. Isso se deve à natureza ordenada do array.
Linha Principal
A linha result += right - left em nosso algoritmo é fundamental. Ela calcula de forma eficiente o número de pares válidos que podem ser formados com o elemento esquerdo e todos os elementos até o elemento direito. Isso se baseia no raciocínio de que todos esses elementos, quando somados entre direita e esquerda, produzirão somas menores que o alvo. Ao usar esta linha, adicionamos a contagem de todos esses pares válidos ao nosso resultado em um único passo, demonstrando a eficiência da técnica dos dois ponteiros.
Análise de Complexidade
Conclusão
Em nossas soluções para o Problema “2824. Count Pairs Whose Sum is Less than Target” usando a técnica dos dois ponteiros, tanto a complexidade de tempo quanto a de espaço desempenham papéis significativos.
Complexidade de Tempo:
- Ordenando o Array: O primeiro passo do nosso algoritmo envolve ordenar o array. Tanto em Java quanto em Python, a operação de ordenação normalmente tem uma complexidade de tempo de O(n log n), onde n é o número de elementos no array.
- Iterando com Dois Ponteiros: Uma vez que o array está ordenado, usamos um loop while para iterar pelo array com nossos dois ponteiros. Esta iteração, no pior caso, percorre o array uma vez, levando a uma complexidade de tempo de O(n).
- Complexidade de Tempo Total: Ao combinar esses passos, o fator dominante é a etapa de ordenação, fazendo com que a complexidade de tempo total da nossa solução seja O(n log n).
Complexidade de Espaço:
- Nas implementações em Java e Python, usamos apenas um número fixo de variáveis (ponteiros e contadores). Não há espaço adicional que cresça com o tamanho do array de entrada.
- Portanto, a complexidade de espaço da nossa solução é O(1), também conhecida como complexidade de espaço constante. Isso significa que o espaço necessário pelo nosso algoritmo não aumenta com o tamanho dos dados de entrada.
Comparando com a Solução Utilizando Foça Bruta
Esta análise mostra que nossa solução é eficiente, especialmente para grandes conjuntos de dados. A complexidade de tempo O(n log n) é muito mais performática do que uma abordagem de força bruta, que normalmente teria uma complexidade de tempo de O(n²). Além disso, a complexidade de espaço constante implica que nossa solução é eficiente em termos de memória, uma consideração importante em aplicações do mundo real.
Usar a Técnica dos Dois Ponteiros não apenas simplificou o problema, mas também proporcionou uma excelente demonstração de eficiência algorítmica tanto em Java quanto em Python.
Pontos Principais:
- Técnica dos Dois Ponteiros: Uma solução elegante para problemas envolvendo sequências ou arrays, especialmente quando combinada com a ordenação.
- Eficiência: Nossas soluções em Java e Python destacam a importância de considerar as complexidades de tempo e espaço ao codificar soluções. A técnica dos dois ponteiros, com sua complexidade de tempo O(n log n) e complexidade de espaço O(1), prova ser uma técnica importante no design de algoritmos.
- Aplicabilidade: Esta técnica é versátil e pode ser aplicada a uma variedade de problemas, especialmente aqueles que envolvem arrays ordenados.
Próximos Passos:
- Experimentar: Tente aplicar a técnica dos dois ponteiros a outros problemas.
- Analisar: Sempre considere a complexidade de tempo e espaço de suas soluções.
- Engajar: Compartilhe suas experiências e soluções com a comunidade. Se você já tentou resolver o “2824. Count Pairs Whose Sum is Less than Target” ou um problema semelhante usando uma abordagem diferente, adoraríamos ouvir sobre isso nos comentários!
Referências
Cracking the Coding Interview’ é um best-seller renomado e um favorito pessoal – um livro indispensável na preparação para entrevistas técnicas!
Designing Data-Intensive Applications: é uma referência para criar aplicações escaláveis, robustas e de alto desempenho!