325. Maximum Size Subarray Sum Equals k (Medium)
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?
Solution 1: Subsum 42ms
这道题给我们一个一维数组nums,让我们求和为k最大子数组,默认子数组必须连续,题目中提醒我们必须要在O(n)的时间复杂度完成,我试了下brute force无法通过OJ,那么根据题目中的提示标签,我们需要用哈希表和累积和来做,关于累积和的用法可以参看我之前的博客Range Sum Query - Immutable,那么建立累积和的好处显而易见,如果当前累积和正好等于k,那么从开头到此位置的子数组就是一个符合要求的解,但不一定是最长的子数组,而使用哈希表来建立累积和和其坐标之间的映射,我们就从题目中给的例子进行分析:
nums: [1, -1, 5, -2, 3], k = 3
sums: [1, 0, 5, 3, 6]
我们可以看到累积和的第四个数字为3,和k相同,则说明前四个数字就是符合题意的一个子数组,再来看第二个例子:
nums: [-2, -1, 2, 1], k = 1
sums: [-2, -3, -1, 0]
我们发现累积和中没有数字等于k,但是我们知道这个例子的答案是[-1, 2],那么我们看累积和数组的第三和第四个数字,我们是否能看出一些规律呢,没错,第四个数字0减去k,得到第三个数字,这就是规律,这也是累积和求区间和的方法,但是由于累计和数组中可能会有重复数字,而哈希表的关键字不能相同,比如下面这个例子:
nums: [1, 0, -1], k = -1
sums: [1, 1, 0]
我们发现累积和数组的第一个和第二个数字都为1,那么如何建立映射呢,我想的是用一个一维数组将其都存起来,然后比较的话就比较数组中的第一个数字,当我们建立完哈希表后,开始遍历这个哈希表,当累积和跟k相同时,我们更新res,不相同的话我们检测当前值减去k得到的值在哈希表中存不存在,如果存在就更新结果,参见代码如下:
class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
if (nums.empty()) return 0;
vector<int> sum = nums;
unordered_map<int, vector<int>> m;
m[sum[0]].push_back(0);
for (int i = 1; i < nums.size(); ++i) {
sum[i] += sum[i-1];
m[sum[i]].push_back(i);
}
int res = 0;
for (auto& it:m) {
if (it.first == k) res = max(res, it.second.back()+1);
else if (m.count(it.first-k)) { // sum[a]-sum[b]=k
res = max(res, it.second.back()-m[it.first-k][0]);
}
}
return res;
}
};
Solution 2: 46ms
然而当我上网看大神们的解法时,才发现我图样图森破,根本不需要我写的那么复杂,我们不需要另外创建一个累积和的数组,而是直接用一个变量sum边累加边处理,而且我们哈希表也完全不用建立和一维数组的映射,只要保存第一个出现该累积和的位置,后面再出现直接跳过,这样算下来就是最长的子数组,想出这解法的人你咋不上天呢,参见代码如下:
class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
int sum = 0, res = 0;
unordered_map<int,int> m;
for (int i = 0; i < nums.size(); ++i) {
sum += nums[i];
if (sum == k) res = i+1;
else if (m.count(sum-k)) res = max(res, i-m[sum-k]);
if (!m.count(sum)) m[sum] = i;
}
return res;
}
};