325. Maximum Size Subarray Sum Equals k

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
Output: 4 
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.

Example 2:

Input: nums = [-2, -1, 2, 1], k = 1
Output: 2 
Explanation: The subarray [-1, 2] sums to 1 and is the longest.

Follow Up: Can you do it in O(n) time?

利用hashmap紀錄preSum對應到的index的關係，維護一個sum variable紀錄從頭到當前這個index的和，然後如果遇到sum等於k的情況，那麼就是從頭到現在的subarray是符合條件的，所以讓res等於index + 1。如果hashmap裡有sum - k這個key，那麼說明從mp[sum - k]這個index之後到當前這個index的subarray是符合條件的。另外在掃描每一個數的時候會有一個sum，如果這個sum沒有在hashmap裡，那麼就可以加進去，如果有這個key的話就跳過，因為想要有最長的subarray，所以越早加入hashmap的value越好。

// O(n) Hashmap
int maxSubArrayLen(vector<int>& nums, int k) { // time: O(n); space: O(n)
    unordered_map<int, int> mp; // preSum -> index
    int res = 0, sum = 0;
    for (int i = 0; i < nums.size(); ++i) {
        sum += nums[i];
        if (sum == k) {
            res = i + 1;
        } else if (mp.count(sum - k)) {
            res = max(res, i - mp[sum - k]);
        }
        if (!mp.count(sum)) mp[sum] = i;
    }
    return res;
}