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:
1 <= nums.length <= 3 * 104nums[i] is either 0 or 1.0 <= goal <= nums.length
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
| class Solution:
def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
cnt = Counter({0: 1})
ans = s = 0
for v in nums:
s += v
ans += cnt[s - goal]
cnt[s] += 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int numSubarraysWithSum(int[] nums, int goal) {
int[] cnt = new int[nums.length + 1];
cnt[0] = 1;
int ans = 0, s = 0;
for (int v : nums) {
s += v;
if (s - goal >= 0) {
ans += cnt[s - goal];
}
++cnt[s];
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int numSubarraysWithSum(vector<int>& nums, int goal) {
int cnt[nums.size() + 1];
memset(cnt, 0, sizeof cnt);
cnt[0] = 1;
int ans = 0, s = 0;
for (int& v : nums) {
s += v;
if (s - goal >= 0) {
ans += cnt[s - goal];
}
++cnt[s];
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
| func numSubarraysWithSum(nums []int, goal int) (ans int) {
cnt := map[int]int{0: 1}
s := 0
for _, v := range nums {
s += v
ans += cnt[s-goal]
cnt[s]++
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| /**
* @param {number[]} nums
* @param {number} goal
* @return {number}
*/
var numSubarraysWithSum = function (nums, goal) {
const cnt = new Array(nums.length + 1).fill(0);
cnt[0] = 1;
let ans = 0;
let s = 0;
for (const v of nums) {
s += v;
if (s >= goal) {
ans += cnt[s - goal];
}
++cnt[s];
}
return ans;
};
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| /**
* @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;
};
|
