1844 · subarray sum equals to k II
Medium
Description
Solution27
Notes
Discuss55
Leaderboard
Record
Description
Given an array of integers and an integer k, you need to find the minimum size of continuous no-empty subarrays whose sum equals to k, and return its length.
if there are no such subarray, return -1.
Only $39.9 for the “Twitter Comment System Project Practice” within a limited time of 7 days!
WeChat Notes Twitter for more information（WeChat ID jiuzhang15）
the integer nums[i] may lower than 0
Example
Example1
Input:
nums = [1,1,1,2] and k = 3
Output:
2
Example2
Input:
nums = [2,1,-1,4,2,-3] and k = 3
Output:
2
解法1：presums + hashmap
注意：这种有正有负的数组，不可以用滑动窗口，因为当窗口和大于k时，不能确定怎么移动窗口。
class Solution {
public:
/**
* @param nums: a list of integer
* @param k: an integer
* @return: return an integer, denote the minimum length of continuous subarrays whose sum equals to k
*/
int subarraySumEqualsKII(vector<int> &nums, int k) {
int n = nums.size();
if (n == 0) return k == 0;
vector<int> presums(n + 1, 0);
unordered_map<int, int> mp; //<presum, index>
mp[0] = 0;
int minLen = INT_MAX;
for (int i = 1; i <= n; i++) {
presums[i] = presums[i - 1] + nums[i - 1];
if (mp.find(presums[i] - k) != mp.end()) {
minLen = min(minLen, i - mp[presums[i] - k]);
}
mp[presums[i]] = i;
}
return minLen == INT_MAX ? -1 : minLen;
}
};