108th LeetCode Weekly Contest Binary Subarrays With Sum

发布时间：2020-12-14 04:16:59 所属栏目：大数据来源：网络整理

导读：In an array? A ?of? 0 s and? 1 s,how many?non-empty?subarrays have sum? S ? ? Example 1: Input: A = [1,1,1],S = 2 Output: 4 Explanation: The 4 subarrays are bolded below: [1,1] [1,1] ? Note: A.length = 30000 0 = S = A.length A[i] ?is eithe

In an array?A?of?0s and?1s,how many?non-empty?subarrays have sum?S?

Example 1:

Input: A = [1,1,1],S = 2 Output: 4 Explanation: The 4 subarrays are bolded below: [1,1] [1,1]

Note:

A.length <= 30000
0 <= S <= A.length
A[i]?is either?0?or?1.

通用解法就是求连续数组的和有多少个，这种题代码都不会变的

把和存起来，给后面的数字-S看有没有这个和，有的话加起来，然后a[ans]++说明又存在符合条件的解了

class Solution {
public:
    int numSubarraysWithSum(vector<int>& A,int S) {
       long long ans = 0;
       long long k=0;
       map<long long,long long>a;
       a[0]=1;
       int len = A.size();
       for(int i=0;i<len;i++){
        ans+=A[i];
        if(ans>=S){
            k+=a[ans-S];
        }
        a[ans]++;
       }
       return k;
    }
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!