Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Example 1:
Input:nums = [1,1,1], k = 2 Output: 2
Note:
- The length of the array is in range [1, 20,000].
- The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].
A:
--------就是按照 和的长度,一个个加起来,看是否是结果。-------------这个用的空间最小----------------
class Solution { public: int subarraySum(vector<int>& nums, int k) { int n = nums.size(); int res = 0; vector<int> curSum(n,0); for(int curLen = 1; curLen <= n; curLen++) { for(int i = 0; i+curLen <= n; ++i) { curSum[i] += nums[i+curLen-1]; if(curSum[i] == k) ++res; } } return res; } };
------------------------ 这个最快--------------
class Solution {
public: int subarraySum(vector<int>& nums, int k) { unordered_map<int, int> m = {{0, 1}}; // initialize with m[0] = 1 int count = 0, sum = 0; for (int i = 0; i < nums.size(); i++) { sum += nums[i]; if (m.find(sum - k) != m.end()) { count += m[sum - k]; } m[sum]++; } return count; } };
No comments:
Post a Comment