Finding Subarrays with a Target Sum in Java: A Beginner's Guide

 

PROGRAM: Finding a Subarray with a Target Sum in Java

This program helps in identifying subarrays in a given array whose elements add up to a specific target sum (k). It takes input from the user for the size of the array, its elements, and the target sum. It then iterates through the array to find and display all subarrays that meet the criteria.

---

CODE

import java.util.*;

class kth_subarray {

    int a[], n, k = 0;

    // Constructor to initialize default values

    kth_subarray() {

        n = 0;

        k = 0;

    }

    // Method to take user input

    void input() {

        Scanner sc = new Scanner(System.in);

        System.out.println("Enter the size of the array: ");

        n = sc.nextInt();

        a = new int[n];

        System.out.println("Enter the elements: ");

        for (int i = 0; i < n; i++) {

            a[i] = sc.nextInt();

        }

        System.out.println("Enter your target: ");

        k = sc.nextInt();

    }

    // Method to find and print subarrays with sum equal to target

    void subarray() {

        System.out.print("[ ");

        for (int i = 0; i < n; i++) {

            int sum = a[i];

            for (int j = i + 1; j < n; j++) {

                sum = sum + a[j];

                if (sum == k) {

                    for (int x = 0; x <= j; x++) {

                        System.out.print(a[x] + " ");

                    }

                    break;

                }

            }

        }

        System.out.print("]");

    }

    // Main method to execute the program

    public static void main(String[] args) {

        kth_subarray ob = new kth_subarray();

        ob.input();

        ob.subarray();

    }

}

---------------------------------------------------------------------------------------------------------------------------------

EXAMPLE INPUT/OUTPUT

Input:

mathematica
Enter the size of the array: 
5
Enter the elements: 
1 2 3 4 5
Enter your target: 
5

Output:

css
[ 1 2 3 4 5 ]

---

LOGIC

1. Input the Array and Target:

   • The size of the array (n) and its elements are taken as input.
   • A target value (k) is also entered to identify subarrays whose sum equals this target.

2. Iterate Over Subarrays:

   • The program uses nested loops to calculate the sum of elements from every possible subarray.
   • The outer loop starts at each element in the array.
   • The inner loop adds subsequent elements to form a subarray and checks if the sum equals the target.

3. Print Subarray:

   • If the sum equals the target, it prints the subarray.

4. Efficiency:

   • This approach uses two loops, making the time complexity $O(n^2)$. For small datasets, this method is efficient, but for larger datasets, optimizing with sliding window techniques or hash maps is recommended.