Reference: LeetCode

Difficulty: Medium

## Problem

Given an array

`nums`

and a target value`k`

, find the maximum length of a subarray that sums to`k`

. If there isn’t one, return`0`

instead.

**Note:** The sum of the entire `nums`

array is guaranteed to fit within the 32-bit signed integer range.

**Example:**

1 | Input: nums = [1, -1, 5, -2, 3], k = 3 |

**Follow up:** Can you do it in $O(N)$ time?

## Analysis

### Brute-Force

Calculate sum for each possible subarray. The sum can be accumulated.

1 | public int maxSubArrayLen(int[] nums, int k) { |

**Time:** $O(N^2)$**Space:** $O(1)$

### Hash Map

Based on the idea in `560. Subarray Sum Equals K`

, we need to make some modifications.

- The hash map stores pairs
`<prefixSum, index>`

. - Size of the subarray is
`i - map.get(sum - k)`

. There is no`+1`

required since the leftmost element is not included. - The map should be initialized with
`<0, -1>`

based on the second point above. - We only store the earliest index of a specific prefix sum, although there are multiple indices.
**The earliest index gives us a larger size.**

1 | [1, -1, 5, -2, 3], k = 3 |

Go through these two examples to have a better understanding.

1 | public int maxSubArrayLen(int[] nums, int k) { |

**Time:** $O(N)$**Space:** $O(N)$