Given an array arr[] containing integers and an integer k, your task is to find the…
- User
Given an array arr[] containing integers and an integer k, your task is to find the length of the longest subarray where the sum of its elements is equal to the given value k. It is guaranteed that a valid subarray exists.
Examples:
Input: arr[] = [10, 5, 2, 7, 1, 9], k = 15 Output: 4 Explanation: The subarray [5, 2, 7, 1] has a sum of 15 and length 4. in java
- Assistant
To solve the problem of finding the length of the longest subarray with a sum equal to a given value
k, an efficient approach is to use a HashMap to keep track of cumulative sums and their corresponding indices. This method ensures a time complexity of O(n), wherenis the number of elements in the array.Here's a step-by-step explanation and the corresponding Java implementation:
-
Initialize Variables:
maxLento store the maximum length of the subarray found.sumto keep track of the cumulative sum as we iterate through the array.- A
HashMapcalledsumMapto store the cumulative sum and the earliest index at which this sum occurs.
-
Iterate Through the Array:
- At each step, add the current element to
sum. - If
sumis equal tok, updatemaxLento the current index + 1 (since array indices start at 0). - Check if
(sum - k)exists in thesumMap. If it does, it means there's a subarray ending at the current index with a sum ofk. UpdatemaxLenaccordingly. - If the
sumis not already insumMap, add it with the current index. We store the earliest occurrence to maximize the length of the subarray.
- At each step, add the current element to
-
Return the Result:
- After iterating through the array,
maxLenwill hold the length of the longest subarray with sumk.
- After iterating through the array,
Here is the complete Java program implementing the above logic:
import java.util.HashMap; public class LongestSubarrayWithSumK { /** * Finds the length of the longest subarray with sum equal to k. * * @param arr The input array of integers. * @param k The target sum. * @return The length of the longest subarray with sum equal to k. */ public static int longestSubarrayWithSumK(int[] arr, int k) { // HashMap to store (cumulative_sum, earliest_index) HashMap<Integer, Integer> sumMap = new HashMap<>(); int maxLen = 0; // To store the maximum length found int sum = 0; // To store cumulative sum for (int i = 0; i < arr.length; i++) { sum += arr[i]; // If cumulative sum equals to k, update maxLen if (sum == k) { maxLen = i + 1; } // If (sum - k) is present in sumMap, there exists a subarray // ending at index i with sum equal to k if (sumMap.containsKey(sum - k)) { int prevIndex = sumMap.get(sum - k); int subarrayLen = i - prevIndex; if (subarrayLen > maxLen) { maxLen = subarrayLen; } } // Store the first occurrence of the cumulative sum if (!sumMap.containsKey(sum)) { sumMap.put(sum, i); } } return maxLen; } // Example usage public static void main(String[] args) { int[] arr = {10, 5, 2, 7, 1, 9}; int k = 15; int result = longestSubarrayWithSumK(arr, k); System.out.println("Length of the longest subarray: " + result); // Output: Length of the longest subarray: 4 } }Explanation of the Example:
Given the array
arr = [10, 5, 2, 7, 1, 9]andk = 15:- The subarray
[5, 2, 7, 1]sums up to15and has a length of4. - This is the longest such subarray in the given array.
Output:
Length of the longest subarray: 4Key Points:
- Using a
HashMapallows us to achieve linear time complexity by avoiding the need to check all possible subarrays. - Storing the earliest occurrence of a cumulative sum ensures that we maximize the length of the subarray when a suitable sum difference is found.
- This approach works for arrays containing positive, negative, and zero values.
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.