This article is participating in Python Theme Month. See the link for details

Topic describes

This is 930 on LeetCode. And the same binary subarray, medium difficulty.

Tag: “prefix and”, “hash table”, “double pointer”

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 in bold below, there are four subarrays that satisfy the problem: [1,0,1,0,1] [1,0,1,0,1] [1,0,1,0,1]Copy the code

Example 2:

Input: nums = [0,0,0,0], goal = 0 Output: 15Copy the code

Tip:

  • 1 <= nums.length <= 3 *
    1 0 4 10^4
  • Nums [I] is either 0 or 1
  • 0 <= goal <= nums.length

Prefix and + hash table

A simple idea is to compute the prefix numsnumsnums and the array sumsumsum, then scan numsnumsnums from front to back, for the right endpoint RRR, The sum of [0,r][0, r][0,r] [0,r] continuous segment can be obtained in O(1)O(1)O(1) complexity by prefix and array. According to the exclusion principle, we also need to obtain some left endpoint LLL, Make [0, r] [0, r] [0, r] minus [0, l – 1] [l – 0, 1] is [0, l – 1) and for the TTT, which satisfy the sum [r] – sum = [l – 1] tsum [r] – sum] [l – 1 = tsum [r] – sum = [l – 1] t, In this case, hash table is used to record the occurrence times of scanned sum[I]sum[I], which can achieve O(1)O(1)O(1) O to obtain the number of left endpoints that meet the requirements.

This method is applicable to other cases where nums[I]nums[I]nums[I] values are not fixed as 000 or 111.

Java code:

class Solution {
    public int numSubarraysWithSum(int[] nums, int t) {
        int n = nums.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0.1);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int r = sum[i + 1], l = r - t;
            ans += map.getOrDefault(l, 0);
            map.put(r, map.getOrDefault(r, 0) + 1);
        }
        returnans; }}Copy the code

Python 3 code:

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) - >int:
        n = len(nums)
        presum = [0] + list(accumulate(nums))
        hashmap = defaultdict(int, {0:1})
        ans = 0
        for i in range(n):
            r = presum[i+1]
            l = r - goal
            ans += hashmap[l]
            hashmap[r] += 1
        return ans
Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

Double pointer

A slightly less general approach is to use nums[I]nums[I] without negative weights.


n u m s [ i ] nums[i] The absence of negative weights means that prefixes and arrays must have (non-strictly) monotonically increasing properties.

It is not difficult to prove that given TTT, when our right endpoint RRR moves to the right, the left endpoint LLL satisfying the condition must move to the right.

In implementation, we can use two left endpoints, L1L1L1 and L2L2L2, to represent the set of left endpoints that meet the requirements given the right endpoint RRR, while s1S1S1 and s2s2S2 respectively represent the sum of the two endpoints to RRR.

Java code:

class Solution {
    public int numSubarraysWithSum(int[] nums, int t) {
        int n = nums.length;
        int ans = 0;
        for (int r = 0, l1 = 0, l2 = 0, s1 = 0, s2 = 0; r < n; r++) {
            s1 += nums[r];
            s2 += nums[r];
            while (l1 <= r && s1 > t) s1 -= nums[l1++];
            while (l2 <= r && s2 >= t) s2 -= nums[l2++];
            ans += l2 - l1;
        }
        returnans; }}Copy the code

Python 3 code:

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) - >int:
        n = len(nums)
        ans = l1 = l2 = s1 = s2 = 0
        for r in range(n):
            s1 += nums[r]
            s2 += nums[r]
            while l1 <= r and s1 > goal:
                s1 -= nums[l1]
                l1 += 1
            while l2 <= r and s2 >= goal:
                s2 -= nums[l2]
                l2 += 1
            ans += l2 - l1
        return ans
Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

The last

This is the No.930 of our “Brush through LeetCode” series, which started on 2021/01/01. There are altogether 1916 topics on LeetCode by the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.