KK's blog

每天积累多一些

0%

LeetCode 930 Binary Subarrays With Sum

Posted on Edited on Disqus:

LeetCode



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 104*nums[i]is either0or1. *0 <= goal <= nums.length`

题目大意：

有0和1组成的字符串，求所有子数组的和等于goal的个数

解题思路Presum(推荐)：

求子数组和第一时间想到presum，然后就是presum-goal是否在hashmap中，类似于Two sum。

解题步骤：

N/A

注意事项：

  1. presum初始值为0，因为如果单元素数组，才能得到它的差值。
  2. val_to_freq的计算要在循环中，类似于Two sum，不能提前用Counter计算，否则会有重复，比如[0, 0], goal=0, 不应该为4.

Python代码：

1
2
3
4
5
6
7
8
9
10
def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
	presum = [0]
	for i in range(len(nums)):
		presum.append(presum[-1] + nums[i])
	val_to_freq, res = collections.defaultdict(int), 0
	for i in range(len(presum)):
		if presum[i] - goal in val_to_freq:
			res += val_to_freq[presum[i] - goal]
		val_to_freq[presum[i]] += 1 #attn
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

算法II解题思路Sliding Window：

此法虽然空间复杂度较优，但较难想。求字串的和可以考虑用Two pointers两边夹。这里求所有可能性，比如0011100, goal=3, 必须包括前缀0和后缀0，所以用Two pointers最长串的模板
类似于LeetCode 340 Longest Substring with At Most K Distinct Characters，不满足条件为窗口和大于goal，所以满足条件为小于等于goal(类似于at most k)。
所以要用at_most(goal) - at_most(goal - 1)才能得到最后结果。
计算的时候，是i-left+1代表窗口和<=subgoal的以nums[i]为结尾的子数组个数，比如10101, i指向最后一个1, left指向第一个0, res是4个，对应1, 01, 101, 0101

注意事项：

  1. 模板满足条件在内循环外，所以计算结果在内循环结束后。
  2. subgoal如果小于0，返回0。比如goal为0，nums=[0,0]

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
	def at_most(subgoal):
		if subgoal < 0: #attn
			return 0
		window_sum, left, res = 0, 0, 0
		i = 0
		for i in range(len(nums)):
			window_sum += nums[i]
			while window_sum > subgoal:
				window_sum -= nums[left]
				left += 1
			res += i - left + 1 # ending with nums[i]
		return res

	return at_most(goal) - at_most(goal - 1)

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

Free mock interview