Encontrar um subarray com uma determinada soma é um problema comum que frequentemente aparece na codificação de entrevistas e na programação competitiva. Este problema pode ser resolvido usando várias técnicas, cada uma com suas próprias compensações em relação à complexidade do tempo e da complexidade do espaço. Neste artigo, exploraremos várias abordagens para resolver o problema de encontrar um subarray com uma determinada soma em Java.

Declaração do problema

Dada uma matriz de números inteiros e uma soma alvo, encontre uma submatriz contínua na matriz que soma a soma fornecida. O problema pode ser dividido em duas variantes principais:

1. Subarray com números positivos: o array contém apenas números positivos.
2. Subarray com números mistos: o array contém números positivos e negativos.

Vamos explorar diferentes métodos para resolver essas variantes.

Abordagem 1: Usando Força Bruta

A abordagem de força bruta envolve verificar todas as submatrizes possíveis e calcular suas somas para ver se alguma delas é igual à soma alvo. Essa abordagem funciona para ambas as variantes, mas é ineficiente para matrizes grandes devido à sua complexidade de tempo quadrática.

Implementação

public class SubarraySumBruteForce {
  public static int[] findSubarrayWithGivenSum(int[] arr, int targetSum) {
    int n = arr.length;
    for (int start = 0; start 
Saída
Subarray found from index 1 to 3

Análise

• Complexidade de tempo: O(n²) devido aos dois loops aninhados iterando pela matriz.
• Complexidade do espaço: O(1) pois nenhum espaço adicional é usado além da matriz de entrada.

Abordagem 2: usando janela deslizante

A abordagem da janela deslizante é eficiente para matrizes contendo apenas números positivos. Esta técnica envolve a manutenção de uma janela de elementos que somam a soma desejada. A janela é expandida adicionando elementos até que a soma exceda o alvo, e contraída removendo elementos desde o início até que a soma seja menor ou igual ao alvo.

Implementação

public class SubarraySumSlidingWindow {
  public static int[] findSubarrayWithGivenSum(int[] arr, int targetSum) {
    int start = 0;
    int currentSum = 0;

    for (int end = 0; end  targetSum && start 
Saída
Subarray found from index 1 to 3

Análise

• Complexidade de tempo: O(n) pois cada elemento é processado no máximo duas vezes.
• Complexidade do espaço: O(1) já que nenhum espaço adicional é necessário.