Longest Subarray With Sum K

Use two nested loops to generate all subarrays. The first loop will decide the starting index of the subarray. The second loop will start from the starting index and generate all possible subarrays from the ‘starting index’. 

At each point, check whether the sum of the current subarray is equal to the required sum. 

If the current sum = ‘k’, check whether the length of the current subarray is greater than the maximum value we have found. If this is true, the length of the current subarray is now the maximum length (we have found so far). Else, we continue.

The steps are as follows:-

// Function to find the longest subarray with sum ‘k’

function longestSubarrayWithSumK(int[] a, int n, int k):

1. Int ‘n’ be the size of array ‘a’ and ‘k’ be the required sum.
2. Initialize a variable ‘maxLength’ to ‘0’, storing the maximum length of the subarray whose sum = ‘k’.
3. Iterate over array ‘a’ and at each iteration:
   • Initialize a variable ‘currentSum’ to ‘0’, storing the sum of the current subarray.
   • Iterate over array ‘a’ from the current index to the end of the array:
     • Add the value of array ‘a’ at the index at which we are currently present.
     • If currentSum == ‘k’
       • maxLength = max(‘maxLength’, ‘length of current subarray’)
4. Return maxLength

We will use two indices: ‘startIndex’ and ‘endIndex’. This algorithm works as follows: We first fix the startIndex and will increase the endIndex (which increases the size of our current subarray). We do this till our sum <= ‘k’, or we are not out of bounds. Now we check our current sum and compare it with ‘k’.

Now we may encounter these cases:

1. sum < k

This will be when our endIndex has reached the end of the array. Now, we can stop our program and return the maximum answer we have found.

1. sum >= k
   • If sum == k

We have found a subarray with the required sum. We will now compare the length of the current subarray with the maximum we have found so far and replace it with the greatest.

We now shift the startIndex (increasing it by one and hence decreasing the size of our window) but subtract the current starting element before increasing.
 

We will increase the startIndex till it is < n, after which we will return our maximum answer,
 

The steps are as follows:-

// Function to find the longest subarray with sum ‘k’

function longestSubarrayWithSumK(int[] a, int n, int k):
 

1. Int ‘n’ be the size of array ‘a’ and ‘k’ be the required sum.
2. Initialize a variable ‘maxLength’ to ‘0’, storing the maximum length of the subarray whose sum = ‘k’.
3. Initialize three more variables, ‘start’ with 0, ‘end’ with -1, and ‘currentSum’ with 0, which correspond to starting index of the subarray, the ending index of the subarray, and the sum of the current subarray, respectively.
4. while ‘start < n’:
   • while (end + 1 < n) AND (currentSum + a[end + 1] <= ‘k’):
     • currentSum += a[end + 1]
     • end += 1
   • if currentSum == k:
     • maxLength = max( maxLength, end - start + 1 )
   • currentSum -= a[start]
   • start += 1
5. Return maxLength