Problem Statement

Given an array of integers nums and an integer k, find the length of the longest subarray that sums to k. If no such subarray exists, return 0.

Examples

Example 1:

• Input: nums = [1, 2, 3, -2, 5], k = 5
• Output: 2
• Explanation: The longest subarray with a sum of 5 is [2, 3], which has a length of 2.

Example 2:

• Input: nums = [-2, -1, 2, 1], k = 1
• Output: 2
• Explanation: The longest subarray with a sum of 1 is [-1, 2], which has a length of 2.

Example 3:

• Input: nums = [3, 4, 7, 2, -3, 1, 4, 2], k = 7
• Output: 4
• Explanation: The longest subarray with a sum of 7 is [7, 2, -3, 1], which has a length of 4.

Constraints:

• 1 <= nums.length <= 2 * 10⁵
• -10⁴ <= nums[i] <= 10⁴
• -10⁹ <= k <= 10⁹

Solution

To solve this problem, we can use a hash map (or dictionary) to keep track of the cumulative sum at each index. The key idea is to use the cumulative sum to quickly determine the length of subarrays that sum up to k. By storing the earliest occurrence of each cumulative sum, we can efficiently check if there is a subarray ending at the current index with the required sum. This approach leverages the relationship between the cumulative sums to find the longest subarray with a sum of k in linear time.

This approach is efficient because it avoids the need for nested loops, which would result in a quadratic time complexity. Instead, by using a hash map to store the cumulative sums, we can achieve a linear time complexity, making the solution scalable for large input sizes.

Step-by-Step Algorithm

1. Initialization:

   • Create an empty hash map (cumMap) to store cumulative sums and their earliest indices.
   • Initialize cumSum to 0 to keep track of the cumulative sum as we iterate through the array.
   • Initialize maxLen to 0 to keep track of the maximum length of the subarray with a sum of k.

2. Iterate through the array:

   • Loop through each element in the nums array using a for loop:
     • Update the cumulative sum:
       • For each element num at index i, update the cumulative sum: cumSum += num.
     • Check if the cumulative sum equals k:
       • If cumSum == k, update maxLen to i + 1 since the entire array from the start to the current index sums to k.
     • Check for a subarray with a sum of k:
       • Calculate cumSum - k.
       • If (cumSum - k) exists in cumMap, it means there is a subarray that sums to k:
         • Update maxLen to the maximum of its current value and the length of this subarray: i - cumMap[cumSum - k].
     • Store the cumulative sum and its index:
       • If cumSum is not already in cumMap, add it with its index i: cumMap[cumSum] = i.

3. Return the maximum length:

   • After the loop ends, return maxLen.

Algorithm Walkthrough

Using the input nums = [1, 2, 3, -2, 5], k = 5:

1. Initialization:

   • cumMap = {}
   • cumSum = 0
   • maxLen = 0

2. Iteration:

   • Index 0, num = 1:
     • Update the cumulative sum: cumSum = 1
     • Check if the cumulative sum equals k: cumSum != k
     • Check for a subarray with a sum of k: cumSum - k = -4 does not exist in cumMap
     • Store the cumulative sum and its index: Add 1 to cumMap: cumMap = {1: 0}
   • Index 1, num = 2:
     • Update the cumulative sum: cumSum = 3
     • Check if the cumulative sum equals k: cumSum != k
     • Check for a subarray with a sum of k: cumSum - k = -2 does not exist in cumMap
     • Store the cumulative sum and its index: Add 3 to cumMap: cumMap = {1: 0, 3: 1}
   • Index 2, num = 3:
     • Update the cumulative sum: cumSum = 6
     • Check if the cumulative sum equals k: cumSum != k
     • Check for a subarray with a sum of k: cumSum - k = 1 exists in cumMap at index 0
     • Update maxLen: maxLen = max(0, 2 - 0) = 2
     • Store the cumulative sum and its index: Add 6 to cumMap: cumMap = {1: 0, 3: 1, 6: 2}
   • Index 3, num = -2:
     • Update the cumulative sum: cumSum = 4
     • Check if the cumulative sum equals k: cumSum != k
     • Check for a subarray with a sum of k: cumSum - k = -1 does not exist in cumMap
     • Store the cumulative sum and its index: Add 4 to cumMap: cumMap = {1: 0, 3: 1, 6: 2, 4: 3}
   • Index 4, num = 5:
     • Update the cumulative sum: cumSum = 9
     • Check if the cumulative sum equals k: cumSum != k
     • Check for a subarray with a sum of k: cumSum - k = 4 exists in cumMap at index 3
     • Update maxLen: maxLen = max(2, 4 - 3) = 2
     • Store the cumulative sum and its index: Add 9 to cumMap: cumMap = {1: 0, 3: 1, 6: 2, 4: 3, 9: 4}

3. Result:

   • The maximum length of a subarray summing to 5 is 2.

Code