Find the Contiguous Subarray with Sum to a Given Value in an array.

Brute Force Solution:

public class ContiguousSubarrayWithSum {
    public static void main(String[] args) {
        int[] arr = { 4, 2, -3, 1, 6 };
        int sum = 4;
        findSubarrayWithSum(arr, sum);
    }

    public static void findSubarrayWithSum(int[] arr, int sum) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int currentSum = 0;
            for (int j = i; j < n; j++) {
                currentSum += arr[j];
                if (currentSum == sum) {
                    System.out.println("Subarray found between indices " + i + " and " + j);
                    return;
                }
            }
        }
        System.out.println("Subarray not found");
    }
}

In this code, we first declare an array arr with some sample values and a variable sum with a given value. We then call the findSubarrayWithSum function, which takes the array and the sum as input, and prints the indices of the contiguous subarray that has the given sum, if found.

Inside the findSubarrayWithSum function, we use two nested loops to iterate through each subarray of the input array. For each subarray, we compute the sum of its elements, and check if the sum is equal to the given value. If the sum is equal to the given value, we print the indices of the subarray and return from the function.

The time complexity of this algorithm is O(n^2), since we are iterating through each subarray using two nested loops.

Optimal Solution:

Now let's look at an optimal solution to find the contiguous subarray with a sum to a given value:

public class ContiguousSubarrayWithSum {
    public static void main(String[] args) {
        int[] arr = { 4, 2, -3, 1, 6 };
        int sum = 4;
        findSubarrayWithSum(arr, sum);
    }

    public static void findSubarrayWithSum(int[] arr, int sum) {
        int n = arr.length;
        int currentSum = 0;
        int start = 0;

        for (int i = 0; i < n; i++) {
            currentSum += arr[i];

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

            if (currentSum == sum) {
                System.out.println("Subarray found between indices " + start + " and " + i);
                return;
            }
        }

        System.out.println("Subarray not found");
    }
}

In this optimized solution, we use a sliding window approach to find the contiguous subarray with the given sum. We first declare an array arr with some sample values and a variable sum with a given value. We then call the findSubarrayWithSum function, which takes the array and the sum as input, and prints the indices of the contiguous subarray that has the given sum, if found.

Inside the findSubarrayWithSum function, we use three variables: currentSum, start, and i. The currentSum variable keeps track of the sum of the current subarray, the start variable keeps track of the starting index of the current subarray, and the i variable is the index of the current element we are considering.

We then iterate through the array using a for loop, and add each element to currentSum. If currentSum becomes greater than sum, we move the start index to the right and subtract the element at that index from currentSum. We continue to do this until currentSum becomes less than or equal to sum.

If currentSum becomes equal to sum, we print the indices of the subarray and return from the function. If we reach the end of the array and haven't found a subarray with the given sum, we print a message saying that the subarray was not found.

The time complexity of this algorithm is O(n), since we are iterating through the array only once.