Maximum Size Subarray Sum Equals k -- LeetCode

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.

Example 1:

Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2:

Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

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

思路：O(n)算法

使用哈希表。记录下nums数组中从下标0到i之间所有数字的和。若该值为k，则更新res。若不等于，则检查该值减去k是否在哈希表中存在，若存在，则说明从之前的某一个位置到i之间的数字之和为k。我们用哈希表记录下每个和以及该和第一次出现时的i。

 1 class Solution {
 2 public:
 3     int maxSubArrayLen(vector<int>& nums, int k) {
 4         vector<int> sum(nums.size(), 0);
 5         unordered_map<int, int> help;
 6         int tot = 0, res = 0;
 7         for (int i = 0, n = nums.size(); i < n; i++)
 8         {
 9             sum[i] = i == 0 ? nums[0] : sum[i - 1] + nums[i];
10             if (sum[i] == k) res = i + 1;
11             else if (help.count(sum[i] - k))
12                 res = max(res, i - help[sum[i] - k]);
13             if (help.count(sum[i]) == 0)
14                 help.insert(make_pair(sum[i], i));
15         }
16         return res;
17     }
18 };