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:

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

## Analysis

### Brute-Force

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

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.

Go through these two examples to have a better understanding.

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

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.
Newest Comments
loading...
Info
Article :
50
Total Count :
82.3k
UV :
PV :
Last Push :