Leetcode 【930. 和相同的二元子数组】【统计「优美子数组」】【974. 和可被 K 整除的子数组】【前缀和思想】

这道题目是经典的求 子数组之和=goal的个数，用map维护。

但是笔者在实现的过程中发现0的情况不是很好出来，问题在于mp[sum]和sum+=num的代码语句存在位置问题。后来看了下代码还是自己没有考虑清楚。

这种类型的题目就是要想清楚你的做法，以及边界条件。

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        map<int,int> mp;
        int n=nums.size();
        // mp[0]=1;
        int sum=0,ans=0;
        for(int i=0;i<n;i++){
            int num=nums[i];
            mp[sum]++;
            sum+=num;
            if(mp[sum-goal]){
                ans+=mp[sum-goal];
            }
        }
        return ans;
    }
};

下面这道题目可以看成上面这道题目的衍生。

这道题目转化成求子数组和为k的个数。一下就能A出来

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        for(int i=0;i<nums.size();i++){
            nums[i]=nums[i]%2;
        }
        int sum=0,ans=0;
        map<int,int> mp;
        for(int i=0;i<nums.size();i++){
            mp[sum]++;
            sum+=nums[i];
            ans+=mp[sum-k];
        }
        return ans;

    }
};

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        map<int,int> mp;
        int sum=0,ans=0;
        int n=nums.size();
        for(int i=0;i<n;i++){
            mp[sum]++;
            sum+=nums[i];
            sum=sum%k;
            ans+=mp[k+sum];
            ans+=mp[sum];
            ans+=mp[sum-k];
        }
        return ans;
    }
};