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)代表子數(shù)組arr[0..i]中所有元素的累加和.
那么, arr[j..i] (0<=j<=i<=arr.length-1)的累加和為s(i) - s(j-1).
變量
sum = 0, 表示從arr[0]開始一直到arr[i]的子數(shù)組累加和.
len = 0, 表示累加和為k的最長子數(shù)組長度.
設(shè)置哈希表
key: 表示出現(xiàn)過的累加和sum
value: 表示某個(gè)累加和sum值出現(xiàn)時(shí), 最早的位置 i.
- 遍歷數(shù)組 *
以遍歷到當(dāng)前元素為arr[i]為例.
- 此時(shí)累加和為sum = sum + arr[i], 查看哈希表中是否存在key為sum - k的記錄.
- 如果哈希表中存在sum-k, 則取出對應(yīng)的value, 記為j. 那么 arr[j+1, i]的累加和為s[i] - s[j] = sum - (sum -k) = k. 因?yàn)閖是累加和為sum-k最早出現(xiàn)的位置, 所以arr[j+1..i]是以arr[i]結(jié)尾的, 累加和為k的最長子數(shù)組. 如果 i - j 大于len, 則更新len.
- 如果哈希表中不存在value為sum-k的記錄, 繼續(xù)步驟2.
- 如果哈希表中不存在累加和為sum的記錄, 將記錄<sum, i>插入到哈希表中
- 繼續(xù)遍歷下一個(gè)元素, 直到所有元素遍歷完.
- 邊界條件*
對于 arr[0..i] 的累加和, 可以表示為 s(i) - s(-1), 即累加和為0的最早出現(xiàn)的位置為-1.
實(shí)現(xiàn)
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;
}
};
