1.题目

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2
Example 2:

Input: nums = [1,2,3], k = 3
Output: 2
 
Constraints:

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

2.思路

一开始想到用前缀和，但后面寻找等于K的子数组时，采用暴力两次遍历，最后超时了。看到网上思路才知道可以用map，保存某一特定前缀和是否出现。若map值为一，表示出现了，总count值则加一，为0则表示没有，总count值不变。妙蛙。这样就可一次遍历完成。
【PS】一般函数遍历不能超过 1 0 8 10^8 108，这题两次遍历明显超了

3.origin思路

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

4.参考思路

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) 
    {
       
      vector<int> ans;  
       //ans.push_back(nums[0]);
        int sum=0; //记录前缀和
         int times=0;
        map<int,int> key;
        key[0]=1;
      for(int i=0;i<nums.size();i++)
      {
         //ans.push_back(ans[i-1]+nums[i]);   
          sum+=nums[i];
         times+=key[sum-k];
         key[sum]+=1;
         
      }
       
       return times;
        
    }
};