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?
算法
先定义s的概念
s(i)代表子数组arr[0..i]中所有元素的累加和.
那么, arr[j..i] (0<=j<=i<=arr.length-1)的累加和为s(i) - s(j-1).
变量
sum = 0, 表示从arr[0]开始一直到arr[i]的子数组累加和.
len = 0, 表示累加和为k的最长子数组长度.
设置哈希表
key: 表示出现过的累加和sum
value: 表示某个累加和sum值出现时, 最早的位置 i.
- 遍历数组 *
以遍历到当前元素为arr[i]为例.
- 此时累加和为sum = sum + arr[i], 查看哈希表中是否存在key为sum - k的记录.
- 如果哈希表中存在sum-k, 则取出对应的value, 记为j. 那么 arr[j+1, i]的累加和为s[i] - s[j] = sum - (sum -k) = k. 因为j是累加和为sum-k最早出现的位置, 所以arr[j+1..i]是以arr[i]结尾的, 累加和为k的最长子数组. 如果 i - j 大于len, 则更新len.
- 如果哈希表中不存在value为sum-k的记录, 继续步骤2.
- 如果哈希表中不存在累加和为sum的记录, 将记录<sum, i>插入到哈希表中
- 继续遍历下一个元素, 直到所有元素遍历完.
- 边界条件*
对于 arr[0..i] 的累加和, 可以表示为 s(i) - s(-1), 即累加和为0的最早出现的位置为-1.
实现
int maxSubarraySumK(std::vector<int>& nums, int target)
{
if (nums.size() == 0)
{
return 0;
}
int maxLen = 0;
std::map<int, int> sum2IndexMap;
sum2IndexMap[0] = -1;
int sum = 0;
for (int i = 0; i < nums.size(); ++i)
{
sum = sum + nums[i];
auto iter = sum2IndexMap.find(sum - target);
if (iter != sum2IndexMap.end())
{
maxLen = std::max(i - iter->second, maxLen);
}
if (sum2IndexMap.find(sum) == sum2IndexMap.end())
{
sum2IndexMap.insert(std::make_pair(sum, i));
}
}
return maxLen;
}
};
