力扣Hot100-T10和为k的子数组（前缀和+哈希表）注意思路

中等

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

提示：

• 1 <= nums.length <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

思路：（忘了负数的情况，不完全对）使用滑动窗口的思想，first指向滑动窗口的起始下标，last指向滑动窗口的最后一个下标。初始状态均指向数组第一个下标：

（1）当sum>k时，说明窗口中总和过多，first向前移动，收缩窗口

（2）sum<k时，过小，last向后移动，扩大窗口

（3）sum=k时 first向前移（可能存在0的情况）

注意：每次移动first,last后要判断移动后是否还存在sum==k;

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int first=0;
        int last=0;
        int sum=0;
        int times=0;
        //注意：不要溢出，负数，
        while(last<nums.size()){
            sum+=nums[last];
            while(sum==k)  //
                {
                    times++; 
                   sum-=nums[first];
                	if(first+1<nums.size())
                	 first++;
                	 else break;
                	 
                }
                 if(sum>k){
                    while(sum>k){//first向前移,sum-nums[first] //1 1 0 0 1 1 3 0 0 4  (4)
            sum-=nums[first]; 
           if(first+1<nums.size())
                	 first++;
                	 else break;
           
            //每移动一次也要判断是否等于
 
            while(sum==k){
                times++;
             sum-=nums[first];  
             if(first+1<nums.size())
                	 first++;
                	 else break;
            
            }
 
            }
                }
               
             if(last+1<nums.size())
                last++;
                else break;
                
                
            
          
           
        }
        return times;
 
 
 
 
 
    }
};

正确思路：使用前缀和+哈希表进行优化 （小红书社招二面出现过）:

（1）首先使用sum[i]统计i小标之前的所有数之和（包括下标i指向的数），因此某一段序列和为k转化为sum[p]-sum[q]=k，;有效解决负数带来的问题。在遍历过程中用value记录前i个数组值得总和，使用哈希表记录，其中sum[value]对应的值表示和为value的数组段。

（2）遍历一遍sum，当前sum[p]已知，k已知，只要判断是否存在sum[q]=sum[p]-k,就能判断当前下标作为开始，是否存在一段数组之和等于k,出现次数times=times+sum[q];

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int times=0;
        map<int,int>sum1;
        int sum[30000];
       
        for(int i=0;i<nums.size();i++){
            if(i==0){
                 sum[0]=nums[0];
        sum1[sum[0]]++;
            }
            else{
                sum[i]=sum[i-1]+nums[i];
            sum1[sum[i]]++;
            }
            
            int need=sum[i]-k;
             //有一个问题：别把当前数算进去,需要-1，当前数之和也为-1
 
            if(sum1.find(need)!=sum1.end()){
                if(need==sum[i]){
                    times+=(sum1[need]-1); //[-1,-1,1]中重复计算了
               
                }
                
                else
                 times+=sum1[need];
 
            }
             if (need==0){//注意【0，1】1，当需要的数为零时不仅要判断0出现的次数还要把没有零的自己算进去
             
                times++;
            }
 
 
 
        }
       
        
        return times;
       
       
 
 
 
 
    }
};