Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there is not one, return 0 instead.
Solution
注意到是 subarray, 所以是连续的。因此我们用 /(map/) 来记录一下当前 /(cursum/) 第一次出现下标位置，所以如果此时的前缀和为 /(sum/) 的话，我们计算出第一次出现 /(sum-k/) 的位置，那么这两者位置的差就是可能的答案
点击查看代码
class Solution {
public:
int maxSubArrayLen(vector<int>&A, int k) {
int n = A.size();
unordered_map<long long,long long>M;
long long sum = 0;
long long max_len = 0;
M[0] = -1;
for(int i = 0; i < n; i++)
{
sum += A[i];
if(M.find(sum) == M.end())
M[sum] = i;
if(M.find(sum - k) != M.end())
{
max_len = max(max_len,i - M[sum - k]);
}
}
return max_len;
}
};
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/289586.html