560. Subarray Sum Equals K
1. Description
Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.
2. Example
Example 1:
Input: nums = [1,1,1], k = 2
Output: 2
Example 2:
Input: nums = [1,2,3], k = 3
Output: 2
3. Constraints
- 1 <= nums.length <= $2 * 10^4$
- -1000 <= nums[i] <= 1000
- $-10^7$ <= k <= $10^7$
4. Solutions
My Accepted Solution(Time Limit Exceeded)
n = i_nums.size()
Time complexity: O($n^2$)
Space complexity: O(1)
class Solution
{
public:
// int subarraySum(vector<int>& nums, int k)
int subarraySum(vector<int> &i_nums, int k)
{
int result = 0;
for(int i = 0; i < i_nums.size(); i++)
{
int sum = 0;
for(int ending = i; ending >= 0; ending--)
{
sum += i_nums[ending];
if(sum == k) result++;
}
}
return result;
}
};
4.1 Hash Table
n = i_nums.size()
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
public:
// int subarraySum(vector<int>& nums, int k)
int subarraySum(vector<int> &i_nums, int k)
{
int result = 0;
unordered_map<int, int> rangeSumTimes{{0, 1}}; // some ranges' sum maybe exactly k
for(int i = 0, sum = 0; i < i_nums.size(); i++)
{
sum += i_nums[i];
result += rangeSumTimes[sum - k];
rangeSumTimes[sum]++;
}
return result;
}
};