Preface explains

Algorithm learning, daily brush record.

Subject to connect

And the same binary subarray

The subject content

Given a binary array, nums, and an integer, goal, ask you to count and return how many non-empty subarrays sum to goal.

A subarray is a contiguous segment of an array.

Example 1:

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

Output: 4

Explanation:

As shown below, there are four subarrays that satisfy the problem:

,0,1,0,1 [1], 1-2-3

,0,1,0,1 [1], the 1-2-3-4

,0,1,0,1 [1], the 2-3-4-5

,0,1,0,1 [1], 3-4-5

Example 2:

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

Output: 15

Tip:

1 <= nums.length <= 3 * 10^4

Nums [I] is either 0 or 1

0 <= goal <= nums.length

The analysis process

Define a collection map that holds the number of prefixes and sums.

Define binary subarray count = 0, prefix and sum.

Iterate over nums, count the number of prefixes and sums from the first element to each element, save them in the set map, and count the number of binary subarrays.

If the prefix and sum already exist in the map, add 1 to the prefix and sum; otherwise, set the prefix and sum to 1.

Add the sum of the first n elements to get the prefix and sum.

Sum [j] -sum [I] = goal, sum[j] -sum [I] = goal, sum[j] -sum [I] = goal, sum[j] -sum [I] = goal The sum of sum[I] in the set map is the sum of the subarray goal. If it is not found, count adds up to 0.

The prefix and sum of the last element are stored in the set map, and the prefix and sum of the last element are added to the prefix and sum of the last element. Sum [j] -sum [I] = goal, goal is the sum of the last element only.

If prefix and sum are added to the set map first, then the prefix and sum of the last element will also be saved in the set map when traversing the last element. According to the previous analysis, there is an extra incorrect data in the set map, which will lead to errors in the result.

To solve the code

Class Solution {public int numSubarraysWithSum(int[] nums, int goal) { Map<Integer, Integer> Map = new HashMap<>(); Int count = 0; // define prefix and int sum = 0; For (int num: nums, nums, nums, nums, nums) Nums) {// If prefix and quantity already exist in the set map, prefix and quantity increment by 1, otherwise set prefix and quantity to 1 map.put(sum, map.getordefault (sum, 0) + 1); Sum += num; Sum [j] -sum [I] = goal, sum[j] -sum [I] = goal, sum[j] -sum [I] = goal The sum of sum[I] in the set map is the sum of the subarray goal. If it is not found, count adds up to 0. The prefix and sum of the last element are stored in the set map, and the prefix and sum of the last element are added to the prefix and sum of the last element. When sum[j] -sum [I] = goal, goal is the sum of the subarray of the last element. If the prefix and sum are added to the set map first, then the prefix and sum of the last element are saved in the set map. According to the previous analysis, the prefix and sum of the last element are saved in the set map. Count += map.getorDefault (sum - goal, 0); count += map.getorDefault (sum - goal, 0); } // Return count; }}Copy the code

Submit the results

It took 21ms to execute, beating 60.31% of users in time, consuming 43.2MB of memory, and beating 9.76% of users in space.

The original link

And the same binary subarray