325.Maximum Size Subarray Sum Equals k¶
Tags: Medium
Hash Table
Links: https://leetcode-cn.com/problems/maximum-size-subarray-sum-equals-k/
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.
Note: The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.
Example 1:
Input: nums = [1, -1, 5, -2, 3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.
Example 2:
Input: nums = [-2, -1, 2, 1], k = 1
Output: 2
Explanation: The subarray [-1, 2] sums to 1 and is the longest.
Follow Up: Can you do it in O(n) time?
class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n = nums.size(); if (!n) return 0;
unordered_map<int, vector<int>> um;
int sum = nums[0];
um[sum].push_back(0);
for (int i = 1; i < n; ++i) {
sum += nums[i];
um[sum].push_back(i);
}
int res = 0;
if (um.find(k) != um.end()) {
res = um[k].back() + 1;
}
sum = 0;
for (int i = 0; i < n; ++i) {
sum += nums[i];
if (um.find(sum + k) != um.end()) {
if (um[sum + k].back() > i) {
res = max(res, um[sum + k].back() - i);
}
}
}
return res;
}
};
这道题和560基本上代码区别只在26行。仍然是利用哈希表去存储前缀和和下标的对应关系。
时间复杂度是O(n)。
当然类似的题目还有209,求最小长度,方法大同小异。