Subarray with given sum in Java with different approaches

Finding a subarray with a given sum is a common problem that often appears in coding interviews and competitive programming. This problem can be solved using various techniques, each with its own trade-offs regarding time complexity and space complexity. In this article, we'll explore multiple approaches to solving the problem of finding a subarray with a given sum in Java.

Problem Statement

Given an array of integers and a target sum, find a continuous subarray in the array that adds up to the given sum. The problem can be divided into two main variants:

1. Subarray with Positive Numbers: The array contains only positive numbers.
2. Subarray with Mixed Numbers: The array contains both positive and negative numbers.

Let's explore different methods to solve these variants.

Approach 1: Using Brute Force

The brute force approach involves checking all possible subarrays and calculating their sums to see if any of them equals the target sum. This approach works for both variants but is inefficient for large arrays due to its quadratic time complexity.

Implementation

public class SubarraySumBruteForce {
  public static int[] findSubarrayWithGivenSum(int[] arr, int targetSum) {
    int n = arr.length;
    for (int start = 0; start < n; start++) {
      int currentSum = 0;
      for (int end = start; end < n; end++) {
        currentSum += arr[end];
        if (currentSum == targetSum) {
          return new int[] {
            start,
            end
          };
        }
      }
    }
    return new int[] {
      -1, -1
    }; // Return -1 if no subarray is found
  }

  public static void main(String[] args) {
    int[] arr = {
      1,
      2,
      3,
      7,
      5
    };
    int targetSum = 12;
    int[] result = findSubarrayWithGivenSum(arr, targetSum);
    if (result[0] != -1) {
      System.out.println("Subarray found from index " + result[0] + " to " + result[1]);
    } else {
      System.out.println("No subarray with given sum found.");
    }
  }
}

Output

Subarray found from index 1 to 3

Analysis

• Time Complexity: O(n²) due to the two nested loops iterating through the array.
• Space Complexity: O(1) as no additional space is used beyond the input array.

Approach 2: Using Sliding Window

The sliding window approach is efficient for arrays containing only positive numbers. This technique involves maintaining a window of elements that add up to the target sum. The window is expanded by adding elements until the sum exceeds the target, and contracted by removing elements from the start until the sum is less than or equal to the target.

Implementation

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

    for (int end = 0; end < arr.length; end++) {
      currentSum += arr[end];

      while (currentSum > targetSum && start < end) {
        currentSum -= arr[start];
        start++;
      }

      if (currentSum == targetSum) {
        return new int[] {
          start,
          end
        };
      }
    }
    return new int[] {
      -1, -1
    }; // Return -1 if no subarray is found
  }

  public static void main(String[] args) {
    int[] arr = {
      1,
      2,
      3,
      7,
      5
    };
    int targetSum = 12;
    int[] result = findSubarrayWithGivenSum(arr, targetSum);
    if (result[0] != -1) {
      System.out.println("Subarray found from index " + result[0] + " to " + result[1]);
    } else {
      System.out.println("No subarray with given sum found.");
    }
  }
}

Output

Subarray found from index 1 to 3

Analysis

• Time Complexity: O(n) as each element is processed at most twice.
• Space Complexity: O(1) since no additional space is needed.

The above is the detailed content of Subarray with given sum in Java with different approaches. For more information, please follow other related articles on the PHP Chinese website!