Given a binary array arr of size N and an integer target, return the number of non-empty subarrays with a sum equal to target.
Note : A subarray is the contiguous part of the array.
Example 1:
Input:
N = 5
target = 2
arr[ ] = {1, 0, 1, 0, 1}
Output: 4
Explanation: The 4 subarrays are:
{1, 0, 1, _, _}
{1, 0, 1, 0, _}
{_, 0, 1, 0, 1}
{_, _, 1, 0, 1}
 
Example 2:
Input:
N = 5
target = 5
arr[ ] = {1, 1, 0, 1, 1}
Output: 0
Explanation: There is no subarray with sum equal to target.
Your Task:
You don't need to read input or print anything. Your task is to complete the function numberOfSubarrays() which takes the array arr, interger N and an integer target as input and returns the number of subarrays with a sum equal to target.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ target ≤ N

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Amortized analysis

Starter code: #User function Template for python3



class Solution:

    def numberOfSubarrays(self, arr, N, target):

        # Code here

Solutions:
class Solution:

	def numberOfSubarrays(self, nums, N, goal):
		count = 0
		window_sum = 0
		window_start = 0
		sum_dict = {0: 1}
		for window_end in range(len(nums)):
			window_sum += nums[window_end]
			if window_sum - goal in sum_dict:
				count += sum_dict[window_sum - goal]
			if window_sum in sum_dict:
				sum_dict[window_sum] += 1
			else:
				sum_dict[window_sum] = 1
		return count


class Solution:

	def numberOfSubarrays(self, Arr, N, k):
		count = 0
		sums = {0: 1}
		sum = 0
		for num in Arr:
			sum += num
			rem = sum - k
			if rem in sums:
				count += sums[rem]
			sums[sum] = sums.get(sum, 0) + 1
		return count


from collections import defaultdict

class Solution:

	def numberOfSubarrays(self, arr, N, target):
		prevsum = defaultdict(lambda : 0)
		res = 0
		curr = 0
		for i in range(0, N):
			curr += arr[i]
			if curr == target:
				res += 1
			if curr - target in prevsum:
				res += prevsum[curr - target]
			prevsum[curr] += 1
		return res


class Solution:

	def atmost(self, arr, target):
		if target < 0:
			return 0
		cs = 0
		s = 0
		res = 0
		for i in range(len(arr)):
			cs = cs + arr[i]
			while cs > target:
				cs = cs - arr[s]
				s = s + 1
			res = res + i - s + 1
		return res

	def numberOfSubarrays(self, arr, N, target):
		return self.atmost(arr, target) - self.atmost(arr, target - 1)


class Solution:

	def numberOfSubarrays(self, arr, N, target):
		d = dict()
		ans = 0
		temp = 0
		for i in range(len(arr)):
			temp += arr[i]
			if temp == target:
				ans += 1
			if temp - target in d:
				ans += d[temp - target]
			d[temp] = d.get(temp, 0) + 1
		return ans


class Solution:

	def numberOfSubarrays(self, arr, N, target):
		return self.atMost(arr, N, target) - self.atMost(arr, N, target - 1)

	def atMost(self, arr, N, target):
		i = 0
		ans = 0
		count = 0
		for j in range(N):
			count = count + arr[j]
			while count > target:
				count = count - arr[i]
				i += 1
			ans += j - i + 1
		return ans


class Solution:

	def numberOfSubarrays(self, arr, N, target):
		return self.sumAtMost(arr, N, target) - self.sumAtMost(arr, N, target - 1)

	def sumAtMost(self, arr, N, target):
		(i, j, ans) = (0, 0, 0)
		state = 0
		while j < N:
			state += arr[j]
			while state > target:
				state -= arr[i]
				i += 1
			ans += j - i + 1
			j += 1
		return ans


class Solution:

	def numberOfSubarrays(self, A, n, S):
		psum = {0: 1}
		curr_sum = 0
		res = 0
		for i in A:
			curr_sum += i
			if curr_sum - S in psum.keys():
				res += psum.get(curr_sum - S)
			psum[curr_sum] = psum.get(curr_sum, 0) + 1
		return res


class Solution:

	def numberOfSubarrays(self, arr, N, target):
		count = 0
		left = 0
		right = 0
		suma = 0
		while left <= right and right < N:
			suma += arr[right]
			if suma > target:
				suma = suma - arr[right]
				right -= 1
				rc = right
				lc = left
				cl = 0
				cr = 0
				while arr[lc] == 0:
					cl += 1
					lc += 1
				while arr[rc] == 0:
					cr += 1
					rc -= 1
				suma = suma - arr[lc]
				left = lc + 1
				count += (cr + 1) * (cl + 1)
			if suma == target and right == N - 1:
				rc = right
				lc = left
				cl = 0
				cr = 0
				while arr[lc] == 0:
					cl += 1
					lc += 1
				while arr[rc] == 0:
					cr += 1
					rc -= 1
				suma = suma - arr[lc]
				left = lc + 1
				count += (cr + 1) * (cl + 1)
			right += 1
		return count
		return count


class Solution:

	def numberOfSubarrays(self, arr, N, target):
		return self.helper(arr, target) - self.helper(arr, target - 1)

	def helper(self, arr, target):
		left = 0
		su = 0
		n = len(arr)
		ans = 0
		for right in range(0, n):
			su += arr[right]
			while su > target:
				su -= arr[left]
				left += 1
			ans += right - left + 1
		return ans


class Solution:

	def numberOfSubarrays(self, arr, N, target):
		return self.C(arr, N, target) - self.C(arr, N, target + 1)

	def C(self, arr, N, target):
		answer = 0
		sm = 0
		i = 0
		for j in range(N):
			sm += arr[j]
			if sm == target:
				while i <= j and sm == target:
					sm -= arr[i]
					i += 1
			answer += i
		return answer


class Solution:

	def numberOfSubarrays(self, arr, N, target):
		sum1 = 0
		j = 0
		d = {}
		count = 0
		while j < N:
			sum1 = sum1 + arr[j]
			if sum1 == target:
				count = count + 1
			if sum1 - target in d:
				count = count + d[sum1 - target]
			if sum1 in d:
				d[sum1] += 1
			else:
				d[sum1] = 1
			j = j + 1
		return count


class Solution:

	def numberOfSubarrays(self, arr, N, target):
		sum = count = 0
		res = dict()
		res[0] = 1
		for i in arr:
			sum += i
			if sum in res:
				res[sum] += 1
			else:
				res[sum] = 1
			if sum - target in res:
				count += res[sum - target]
		return count


class Solution:

	def numberOfSubarrays(self, arr, n, target):
		ans = 0
		j = 0
		cnt = 0
		temp = 0
		for i in range(n):
			cnt += arr[i]
			if cnt == target:
				temp = 0
				while cnt == target and j <= i:
					temp += 1
					cnt -= arr[j]
					j += 1
			ans += temp
		return ans


class Solution:

	def numberOfSubarrays(self, nums, N, goal):
		sum = 0
		count_sum = {}
		count = 0
		for r in range(len(nums)):
			sum += nums[r]
			if sum == goal:
				count += 1
			if count_sum.get(sum - goal, 0):
				count += count_sum[sum - goal]
			count_sum[sum] = 1 + count_sum.get(sum, 0)
		return count


import collections

class Solution:

	def numberOfSubarrays(self, arr, n, k):
		map = collections.defaultdict(int)
		i = 0
		cur = 0
		count = 0
		while i < n:
			cur += arr[i]
			if cur == k:
				count += 1
			if map[cur - k]:
				count += map[cur - k]
			map[cur] += 1
			i += 1
		return count


import collections

class Solution:

	def numberOfSubarrays(self, arr, N, target):
		c = collections.Counter({0: 1})
		psum = res = 0
		for i in arr:
			psum += i
			res += c[psum - target]
			c[psum] += 1
		return res


class Solution:

	def numberOfSubarrays(self, arr, n, target):
		d = {}
		curr = 0
		ans = 0
		for i in range(n):
			curr += arr[i]
			if curr == target:
				ans += 1
			if curr - target in d:
				ans += d[curr - target]
			d[curr] = d.get(curr, 0) + 1
		return ans


class Solution:

	def numberOfSubarrays(self, arr, N, target):
		summa1 = 0
		summa2 = 0
		count = 0
		i = 0
		j = 0
		for item in arr:
			while i < N and summa1 < target:
				summa1 += arr[i]
				i += 1
			while j < N and (summa2 < target or arr[j] == 0):
				summa2 += arr[j]
				j += 1
			if summa1 == target:
				count += j - i + 1
			summa1 -= item
			summa2 -= item
		return count


class Solution:

	def numberOfSubarrays(self, arr, N, target):
		k = {}
		i = 0
		c = 0
		s = 0
		while i < len(arr):
			s += arr[i]
			if s == target:
				c += 1
			if s - target in k:
				c += k[s - target]
			if s not in k:
				k[s] = 1
			else:
				k[s] += 1
			i += 1
		return c


class Solution:

	def numberOfSubarrays(self, arr, N, target):
		s = 0
		c = 0
		di = {}
		for i in range(len(arr)):
			s += arr[i]
			if s == target:
				c += 1
			if s - target in di:
				c += di[s - target]
			if s not in di:
				di[s] = 1
			else:
				di[s] += 1
		return c


from collections import defaultdict

class Solution:

	def numberOfSubarrays(self, a, N, goal):
		(count, currsum) = (0, 0)
		prevsum = defaultdict(int)
		for i in a:
			currsum += i
			if currsum == goal:
				count += 1
			if currsum - goal in prevsum:
				count += prevsum[currsum - goal]
			prevsum[currsum] += 1
		return count


class Solution:

	def numberOfSubarrays(self, arr, N, target):

		def atMostSub(S):
			if S < 0:
				return 0
			res = 0
			i = 0
			for j in range(N):
				S -= arr[j]
				while S < 0:
					S += arr[i]
					i += 1
				res += j - i + 1
			return res
		return atMostSub(target) - atMostSub(target - 1)


class Solution:

	def numberOfSubarrays(self, arr, N, target):
		count = 0
		(i, j) = (0, 0)
		sum_ = 0
		while j < N:
			sum_ += arr[j]
			if sum_ < target:
				j += 1
			elif sum_ == target:
				count += 1
				start = i
				if j == 0 and target == 0:
					j += 1
					continue
				while start < j and sum_ == target:
					sum_ -= arr[start]
					if sum_ != target:
						sum_ += arr[start]
						break
					start += 1
					count += 1
				j += 1
			elif sum_ > target:
				while i <= j and sum_ > target:
					sum_ -= arr[i]
					i += 1
				if i < N and sum_ == target:
					count += 1
					start = i
					while start < j and sum_ == target:
						sum_ -= arr[start]
						if sum_ != target:
							sum_ += arr[start]
							break
						start += 1
						count += 1
					j += 1
				elif i < N:
					j += 1
				else:
					break
		return count


class Solution:

	def numberOfSubarrays(self, arr, N, target):
		h = {0: 1}
		Sum = 0
		count = 0
		for num in arr:
			Sum += num
			if Sum - target in h:
				count += h[Sum - target]
			h[Sum] = h.get(Sum, 0) + 1
		return count


class Solution:

	def numberOfSubarrays(self, arr, N, target):

		def atMostGoal(target):
			if target < 0:
				return 0
			(res, l, s) = (0, 0, 0)
			for r in range(len(arr)):
				s += arr[r]
				while s > target:
					s -= arr[l]
					l += 1
				res += r - l + 1
			return res
		return atMostGoal(target) - atMostGoal(target - 1)


class Solution:

	def numberOfSubarrays(self, arr, N, target):
		ans = 0
		sum = 0
		d = {}
		d[0] = 1
		for i in arr:
			sum += i
			if sum - target in d:
				ans += d[sum - target]
			if sum in d:
				d[sum] += 1
			else:
				d[sum] = 1
		return ans


class Solution:

	def numberOfSubarrays(self, arr, N, target):
		ans = 0
		(s, e, sum) = (0, 0, 0)
		while e < N:
			if sum < target:
				sum += arr[e]
				if sum == target:
					ans += 1
				e += 1
			elif arr[e] == 1:
				while arr[s] == 0 and s < e:
					s += 1
					ans += 1
				sum -= 1
				s += 1
				sum += arr[e]
				ans += 1
				e += 1
			else:
				i = s
				while arr[i] != 1:
					i += 1
					ans += 1
				e += 1
				ans += 1
		while s < e and arr[s] != 1:
			if sum == target:
				ans += 1
			s += 1
		return ans


class Solution:

	def numberOfSubarrays(self, nums, N, goal):
		n = len(nums)
		c = {}
		c[0] = 1
		total = 0
		res = 0
		for i in range(n):
			total += nums[i]
			if total - goal in c:
				res += c[total - goal]
			if total in c:
				c[total] += 1
			else:
				c[total] = 1
		return res


class Solution:

	def numberOfSubarrays(self, arr, N, target):
		m = {}
		su = count = 0
		for i in range(N):
			su += arr[i]
			if su == target:
				count += 1
			if su - target in m.keys():
				count += m[su - target]
			if su not in m.keys():
				m[su] = 1
			else:
				m[su] += 1
		return count


class Solution:

	def numberOfSubarrays(self, a, n, k):

		def find(A, S):
			if S < 0:
				return 0
			res = i = total = 0
			for j in range(len(A)):
				total += A[j]
				while total > S:
					total -= A[i]
					i += 1
				res += j - i + 1
			return res
		return find(a, k) - find(a, k - 1)


class Solution:

	def numberOfSubarrays(self, a, n, k):
		d = {}
		summ = 0
		count = 0
		for i in range(n):
			summ += a[i]
			if summ == k:
				count += 1
			if summ - k in d:
				count += d[summ - k]
			d[summ] = d.get(summ, 0) + 1
		return count


class Solution:

	def numberOfSubarrays(self, a, n, k):
		d = {}
		c = 0
		total = 0
		for i in range(n):
			total += a[i]
			if total == k:
				c += 1
			if total - k in d:
				c += d[total - k]
			d[total] = d.get(total, 0) + 1
		return c


class Solution:

	def numberOfSubarrays(self, arr, N, target):
		dict = {0: 1}
		s = 0
		c = 0
		for i in range(N):
			s += arr[i]
			ch = s - target
			if ch in dict:
				c += dict[ch]
			if s not in dict:
				dict[s] = 1
			else:
				dict[s] += 1
		return c


class Solution:

	def numberOfSubarrays(self, A, N, S):
		l = count = res = s = 0
		for (r, i) in enumerate(A):
			s += i
			if i == 1:
				count = 0
			while l <= r and s >= S:
				if s == S:
					count += 1
				s -= A[l]
				l += 1
			res += count
		return res


class Solution:

	def numberOfSubarrays(self, nums, n, k):
		s = 0
		p = 0
		h = {0: 1}
		for j in nums:
			p += j
			if p - k in h:
				s += h[p - k]
			if p in h:
				h[p] += 1
			else:
				h[p] = 1
		return s


from collections import defaultdict

class Solution:

	def numberOfSubarrays(self, arr, N, target):
		presum = defaultdict(lambda : [])
		presum[0].append(-1)
		curr = 0
		res = 0
		for i in range(N):
			curr += arr[i]
			res += len(presum[curr - target])
			presum[curr].append(i)
		return res


class Solution:

	def numberOfSubarrays(self, arr, n, S):
		l = count = res = s = 0
		for (r, i) in enumerate(arr):
			s += i
			if i == 1:
				count = 0
			while l <= r and s >= S:
				if s == S:
					count += 1
				s += -arr[l]
				l += 1
			res += count
		return res


class Solution:

	def numberOfSubarrays(self, nums, N, goal):
		res = j = count = 0
		for (i, v) in enumerate(nums):
			goal -= v
			if v == 1:
				count = 0
			while j <= i and goal <= 0:
				if goal == 0:
					count += 1
				goal += nums[j]
				j += 1
			res += count
		return res


from collections import defaultdict

class Solution:

	def numberOfSubarrays(self, nums, n, goal):
		my_dict = defaultdict(int)
		(sum_, res) = (0, 0)
		my_dict[0] = 1
		for n in nums:
			sum_ += n
			res += my_dict.get(sum_ - goal, 0)
			my_dict[sum_] += 1
		return res


class Solution:

	def numberOfSubarrays(self, nums, N, goal):
		mapi = [0] * (N + 1)
		sum_ = 0
		mapi[0] = 1
		result = 0
		for num in nums:
			sum_ += num
			if sum_ - goal >= 0:
				result += mapi[sum_ - goal]
			mapi[sum_] += 1
		return result


class Solution:

	def numberOfSubarrays(self, arr, N, target):
		mp = {}
		(sum, ans) = (0, 0)
		mp[0] = 1
		for i in range(len(arr)):
			sum += arr[i]
			if sum - target in mp:
				ans += mp[sum - target]
			if sum in mp:
				mp[sum] += 1
			else:
				mp[sum] = 1
		return ans


class Solution:

	def numberOfSubarrays(self, arr, N, target):
		d = {}
		sm = 0
		ans = 0
		d[0] = 1
		for i in range(N):
			sm += arr[i]
			ans += d.get(sm - target, 0)
			if d.get(sm, -4) == -4:
				d[sm] = 1
			else:
				d[sm] += 1
		return ans


class Solution:

	def numberOfSubarrays(self, arr, N, target):
		(sums, s, count) = ({0: 1}, 0, 0)
		for i in arr:
			s += i
			if s - target in sums:
				count += sums[s - target]
			sums[s] = sums.get(s, 0) + 1
		return count


from collections import defaultdict

class Solution:

	def numberOfSubarrays(self, arr, N, target):
		(count, currsum) = (0, 0)
		prevsum = defaultdict(int)
		for i in arr:
			currsum += i
			if currsum == target:
				count += 1
			if currsum - target in prevsum:
				count += prevsum[currsum - target]
			prevsum[currsum] += 1
		return count


from collections import Counter

class Solution:

	def numberOfSubarrays(self, arr, N, target):
		cntOfSubarrsWithSm = Counter()
		cntOfSubarrsWithSm[0] = 1
		sm = ans = 0
		for v in arr:
			sm += v
			ans += cntOfSubarrsWithSm[sm - target]
			cntOfSubarrsWithSm[sm] += 1
		return ans