LeetCode 930. Binary Subarrays With Sum

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int cnt[30001];
class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        memset(cnt, 0, (nums.size() + 1) * 4);
        cnt[0] = 1;
        int sum = 0, ans = 0;
        for (int num : nums) {
            sum += num;
            if (sum - goal >= 0) ans += cnt[sum - goal];
            ++cnt[sum];
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        int ans = 0;
        for (int l1 = 0, l2 = 0, sum1 = 0, sum2 = 0, r = 0; r < nums.size(); ++r) {
            sum1 += nums[r];
            sum2 += nums[r];
            while (sum1 > goal) sum1 -= nums[l1++];
            while (l2 <= r && sum2 >= goal) sum2 -= nums[l2++];
            ans += l2 - l1;
        }
        return ans;
    }
};