力扣hot10---子串

题目：

思路：

一看到子数组的和，就很容易想到前缀和，求出来前缀和数组后，对前缀和数组进行两重for循环遍历，就大功告成啦！（感觉想一会儿就可以想到）

代码：

C++：

class Solution {
public:
    vector<int> calculate(vector<int>& nums){
        int len=nums.size();
        vector<int> total(len+1,0);
        for(int i=1;i<=len;i++){
            total[i]=total[i-1]+nums[i-1];
        }
        return total;
    }
 
    int subarraySum(vector<int>& nums, int k) {
        //前缀和
        vector<int> total=calculate(nums);
        int res=0;
        int len=total.size();
        for(int i=0;i<len-1;i++){
            for(int j=i+1;j<len;j++){
                if(total[j]-total[i]==k){
                    res++;
                }
            }
        }
        return res;
    }
};

注意一下：（给定空间后，vector可以通过 a [ i ] = 3 来进行赋值）

嗨嗨嗨！因为对应的python过不去呀，那就继续优化！！！

vector<int> total(len+1,0);
for(int i=1;i<=len;i++){
    total[i]=total[i-1]+nums[i-1];
}

优化

for(int i=0;i<len-1;i++){
    for(int j=i+1;j<len;j++){
        if(total[j]-total[i]==k){
            res++;
        }
    }
}

看到这段代码有没有什么想法呢，我们依次遍历元素，假如遍历到了第 i 个元素，那么前 i 个元素的值（此时，元素的值为前缀和数组中的值）就要记录在哈希表中，于是又转换为了两数之和的问题！！！

把上面的代码改为下面的代码就可以啦

for(int i=0;i<len;i++){
    int temp=total[i]-k;
    if(hmap.find(temp)!=hmap.end()){
        res+=hmap[temp];
    }
    hmap[total[i]]+=1;
}

改进后的代码：

class Solution {
public:
    vector<int> calculate(vector<int>& nums){
        int len=nums.size();
        vector<int> total(len+1,0);
        for(int i=1;i<=len;i++){
            total[i]=total[i-1]+nums[i-1];
        }
        return total;
    }
 
    int subarraySum(vector<int>& nums, int k) {
        //前缀和
        vector<int> total=calculate(nums);
        unordered_map<int,int> hmap;
        int res=0;
        int len=total.size();
        /*
        for(int i=0;i<len-1;i++){
            for(int j=i+1;j<len;j++){
                if(total[j]-total[i]==k){
                    res++;
                }
            }
        }
        */
        for(int i=0;i<len;i++){
            int temp=total[i]-k;
            if(hmap.find(temp)!=hmap.end()){
                res+=hmap[temp];
            }
            hmap[total[i]]+=1;
        }
        return res;
    }
};

python：

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        len_nums=len(nums)
        total=[0]*(len_nums+1)
        for i in range(1,len_nums+1):
            total[i]=total[i-1]+nums[i-1]
        res=0
        hmap={}
        len_total=len(total)
        for i in range(0,len_total):
            temp=total[i]-k
            if temp in hmap:
                res+=hmap[temp]
            hmap[total[i]]=hmap.get(total[i],0)+1
        return res

注意：

hmap[total[i]]=hmap.get(total[i],0)+1

total [ i ]不在hmap中时，hmap [ total [ i ] ] += 1会报错