leetcode(12)

leetcode(12)

560. Subarray Sum Equals K

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:

  1. The length of the array is in range [1, 20,000].
  2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

//brute force

class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int size=nums.size();
int total=0;
for(int i=0;i<size;i++)
{
int partsum=0;
for(int j=i;j<size;j++)
{
partsum += nums[j];
if(partsum==k)
total++;
}
}
return total;
}
};

&nbsp;

//using prefix sum and map

class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int size=nums.size();
int total=0;
int partsum=0;
map<int,int> presum;
presum[0]++;
for(int i=0;i<size;i++)
{

//计算prefix sum
partsum += nums[i];

//presum[partsum-k]得到到目前位置为止前面有多少个prefix sum==partsum-k

//就将total加上相应的个数
total += presum[partsum-k];

//将到目前为止相同的prefix sum加1
presum[partsum]++;
}
return total;
}
};




So BadJust So SoGoodCoolPretty Cool (还没人评过分呢!)
Loading...

发表评论

电子邮件地址不会被公开。 必填项已用*标注