README_EN.md

930. Binary Subarrays With Sum

中文文档

Description

Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum goal.

A subarray is a contiguous part of the array.

 

Example 1:

Input: nums = [1,0,1,0,1], goal = 2

Output: 4

Explanation: The 4 subarrays are bolded and underlined below:

[1,0,1,0,1]

[1,0,1,0,1]

[1,0,1,0,1]

[1,0,1,0,1]

Example 2:

Input: nums = [0,0,0,0,0], goal = 0

Output: 15

 

Constraints:

<li><code>1 &lt;= nums.length &lt;= 3 * 10<sup>4</sup></code></li>

<li><code>nums[i]</code> is either <code>0</code> or <code>1</code>.</li>

<li><code>0 &lt;= goal &lt;= nums.length</code></li>

Solutions

Python3

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        counter = Counter({0: 1})
        s = ans = 0
        for num in nums:
            s += num
            ans += counter[s - goal]
            counter[s] += 1
        return ans

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        i1 = i2 = s1 = s2 = j = ans = 0
        n = len(nums)
        while j < n:
            s1 += nums[j]
            s2 += nums[j]
            while i1 <= j and s1 > goal:
                s1 -= nums[i1]
                i1 += 1
            while i2 <= j and s2 >= goal:
                s2 -= nums[i2]
                i2 += 1
            ans += i2 - i1
            j += 1
        return ans

Java

class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        int[] counter = new int[nums.length + 1];
        counter[0] = 1;
        int s = 0, ans = 0;
        for (int num : nums) {
            s += num;
            if (s >= goal) {
                ans += counter[s - goal];
            }
            ++counter[s];
        }
        return ans;
    }
}

class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        int i1 = 0, i2 = 0, s1 = 0, s2 = 0, j = 0, ans = 0;
        int n = nums.length;
        while (j < n) {
            s1 += nums[j];
            s2 += nums[j];
            while (i1 <= j && s1 > goal) {
                s1 -= nums[i1++];
            }
            while (i2 <= j && s2 >= goal) {
                s2 -= nums[i2++];
            }
            ans += i2 - i1;
            ++j;
        }
        return ans;
    }
}

C++

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

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        int i1 = 0, i2 = 0, s1 = 0, s2 = 0, j = 0, ans = 0;
        int n = nums.size();
        while (j < n)
        {
            s1 += nums[j];
            s2 += nums[j];
            while (i1 <= j && s1 > goal) s1 -= nums[i1++];
            while (i2 <= j && s2 >= goal) s2 -= nums[i2++];
            ans += i2 - i1;
            ++j;
        }
        return ans;
    }
};

Go

func numSubarraysWithSum(nums []int, goal int) int {
	counter := make([]int, len(nums)+1)
	counter[0] = 1
	s, ans := 0, 0
	for _, num := range nums {
		s += num
		if s >= goal {
			ans += counter[s-goal]
		}
		counter[s]++
	}
	return ans
}

func numSubarraysWithSum(nums []int, goal int) int {
	i1, i2, s1, s2, j, ans, n := 0, 0, 0, 0, 0, 0, len(nums)
	for j < n {
		s1 += nums[j]
		s2 += nums[j]
		for i1 <= j && s1 > goal {
			s1 -= nums[i1]
			i1++
		}
		for i2 <= j && s2 >= goal {
			s2 -= nums[i2]
			i2++
		}
		ans += i2 - i1
		j++
	}
	return ans
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} goal
 * @return {number}
 */
var numSubarraysWithSum = function (nums, goal) {
    let i1 = 0,
        i2 = 0,
        s1 = 0,
        s2 = 0,
        j = 0,
        ans = 0;
    const n = nums.length;
    while (j < n) {
        s1 += nums[j];
        s2 += nums[j];
        while (i1 <= j && s1 > goal) s1 -= nums[i1++];
        while (i2 <= j && s2 >= goal) s2 -= nums[i2++];
        ans += i2 - i1;
        ++j;
    }
    return ans;
};

...