Given an unsorted array arr[] of N integers and a sum. The task is to count the number of subarrays which add to a given number.
 
Example 1:
Input:
N=5
sum=-10
arr[] = { 10, 2, -2, -20, 10 }
Output:  3
Explanation:
Subarrays with sum -10 are: 
[10, 2, -2, -20], [2, -2, -20, 10]
and [-20, 10].
 
Example 2:
Input:
N=6
sum= 33
arr[] = { 1, 4, 20, 3, 10, 5 }
Output:  1
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function subArraySum() that takes array arr , integer N and integer sum as parameters and returns the count of the subarray which adds to the given sum.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
 
Constraints:
1 ≤ N ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def findSubarraySum(self,arr, n, Sum):  

        #code here

Solutions:
class Solution:

	def findSubarraySum(self, arr, n, k):
		currsum = {}
		currsum[0] = 1
		sums = 0
		count = 0
		for i in range(n):
			sums += arr[i]
			if sums - k in currsum:
				count += currsum[sums - k]
			if sums in currsum:
				currsum[sums] += 1
			else:
				currsum[sums] = 1
		return count


from collections import defaultdict

class Solution:

	def findSubarraySum(self, arr, n, Sum):
		count = 0
		total = 0
		d = defaultdict(lambda : 0)
		for x in arr:
			total += x
			if total - Sum in d:
				count += d[total - Sum]
			if total == Sum:
				count += 1
			d[total] += 1
		return count


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		for i in range(1, n):
			arr[i] += arr[i - 1]
		dic = {}
		dic[0] = 1
		count = 0
		for i in arr:
			if i - s in dic:
				count += dic[i - s]
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		return count


from collections import defaultdict

class Solution:

	def findSubarraySum(self, arr, n, Sum):
		prevSum = defaultdict(lambda : 0)
		res = 0
		currsum = 0
		for i in range(0, n):
			currsum += arr[i]
			if currsum == Sum:
				res += 1
			if currsum - Sum in prevSum:
				res += prevSum[currsum - Sum]
			prevSum[currsum] += 1
		return res


class Solution:

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


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		d = {0: 1}
		ans = 0
		sums = 0
		for i in arr:
			sums = sums + i
			if sums - Sum in d:
				ans = ans + d[sums - Sum]
			if sums in d:
				d[sums] += 1
			else:
				d[sums] = 1
		return ans


class Solution:

	def findSubarraySum(self, arr, n, sum):
		d = {}
		temp = 0
		count = 0
		for i in range(n):
			temp = arr[i] + temp
			if temp - sum == 0:
				count += 1
			if temp - sum in d:
				count += d[temp - sum]
			if temp not in d:
				d[temp] = 1
			else:
				d[temp] += 1
		return count


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		mydict = {0: 1}
		s = 0
		c1 = 0
		for i in arr:
			s += i
			if s - Sum in mydict:
				c1 += mydict[s - Sum]
			if s in mydict:
				mydict[s] += 1
			else:
				mydict[s] = 1
		return c1


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		ps = [0 for i in range(n + 1)]
		for i in range(n):
			ps[i + 1] = ps[i] + a[i]
		ans = 0
		c = dict()
		for x in ps:
			y = x - Sum
			if y in c:
				ans += c[y]
			if x in c:
				c[x] += 1
			else:
				c[x] = 1
		return ans


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		ps = {0: 1}
		current_sum = 0
		ans = 0
		for i in range(n):
			current_sum += arr[i]
			if current_sum - Sum in ps:
				ans += ps[current_sum - Sum]
			if current_sum in ps:
				ps[current_sum] += 1
			else:
				ps[current_sum] = 1
		return ans


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		d = {}
		cursum = 0
		c = 0
		for i in arr:
			cursum += i
			if cursum == Sum:
				c += 1
			if cursum - Sum in d:
				c += d[cursum - Sum]
			if cursum in d:
				d[cursum] += 1
			else:
				d[cursum] = 1
		return c


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		mp = {}
		add = 0
		k = Sum
		ans = 0
		for i in range(n):
			add += arr[i]
			if add == Sum:
				ans += 1
			balance = add - k
			if balance in mp:
				ans += mp[balance]
			if add in mp:
				mp[add] += 1
			else:
				mp[add] = 1
		return ans


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		d = {}
		count = 0
		prefix_sum = 0
		d[0] = 1
		for i in range(n):
			prefix_sum += arr[i]
			if prefix_sum - Sum in d:
				count += d[prefix_sum - Sum]
			try:
				d[prefix_sum] += 1
			except:
				d[prefix_sum] = 1
		return count


from collections import Counter

class Solution:

	def findSubarraySum(self, arr, n, Sum):
		count = 0
		summa = 0
		c = Counter([summa])
		for item in arr:
			summa += item
			count += c[summa - Sum]
			c[summa] += 1
		return count


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		_ = {0: 1}
		count = 0
		sum = 0
		for i in arr:
			sum += i
			if sum - Sum in _:
				count += _[sum - Sum]
			if sum in _:
				_[sum] += 1
			else:
				_[sum] = 1
		return count


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		count = 0
		sum1 = 0
		dict = {}
		for i in range(n):
			sum1 += arr[i]
			if sum1 == Sum:
				count += 1
			if sum1 - Sum in dict:
				count += dict[sum1 - Sum]
			if sum1 in dict:
				dict[sum1] += 1
			else:
				dict[sum1] = 1
		return count


from collections import defaultdict

class Solution:

	def findSubarraySum(self, arr, n, Sum):
		prev_sum = defaultdict(lambda : 0)
		curr_sum = 0
		count = 0
		for i in range(0, n):
			curr_sum += arr[i]
			if curr_sum == Sum:
				count += 1
			if curr_sum - Sum in prev_sum:
				count += prev_sum[curr_sum - Sum]
			prev_sum[curr_sum] += 1
		return count


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		mp = {0: 1}
		summ = 0
		ans = 0
		for i in arr:
			summ += i
			if summ - Sum in mp:
				ans += mp[summ - Sum]
			if summ in mp:
				mp[summ] += 1
			else:
				mp[summ] = 1
		return ans


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		m = {0: 1}
		count = 0
		cur_sum = 0
		for i in range(n):
			cur_sum += arr[i]
			if cur_sum - Sum in m:
				count += m[cur_sum - Sum]
			if cur_sum in m:
				m[cur_sum] += 1
			else:
				m[cur_sum] = 1
		return count


from collections import defaultdict

class Solution:

	def findSubarraySum(self, arr, n, Sum):
		wsum = 0
		ans = 0
		d = defaultdict(int)
		for i in arr:
			wsum += i
			if wsum == Sum:
				ans += 1
			if wsum - Sum in d:
				ans += d[wsum - Sum]
			d[wsum] += 1
		return ans


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		c = 0
		m = {}
		s = 0
		for i in arr:
			s += i
			if s == Sum:
				c += 1
			if s - Sum in m:
				c += m[s - Sum]
			if s not in m:
				m[s] = 1
			else:
				m[s] += 1
		return c


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		hashmap = {}
		pref_sum = [0] * n
		pref_sum[0] = arr[0]
		count = 0
		for i in range(1, n):
			pref_sum[i] = pref_sum[i - 1] + arr[i]
		for i in range(n):
			if pref_sum[i] == Sum:
				count += 1
			temp = pref_sum[i] - Sum
			if temp in hashmap:
				count += hashmap[temp]
			if pref_sum[i] not in hashmap:
				hashmap[pref_sum[i]] = 1
			else:
				hashmap[pref_sum[i]] += 1
		return count


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		dict = {0: 1}
		summ = 0
		cnt = 0
		for i in arr:
			summ += i
			if summ - Sum in dict:
				cnt += dict[summ - Sum]
			if summ in dict:
				dict[summ] += 1
			else:
				dict[summ] = 1
		return cnt


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		count = 0
		cur_sum = 0
		sum_dict = {}
		for x in arr:
			cur_sum += x
			if cur_sum == Sum:
				count += 1
			diff = cur_sum - Sum
			if diff in sum_dict:
				count += sum_dict[diff]
			if cur_sum in sum_dict:
				sum_dict[cur_sum] += 1
			else:
				sum_dict[cur_sum] = 1
		return count


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		sum1 = 0
		a = {0: 1}
		res = 0
		for i in range(n):
			sum1 = sum1 + arr[i]
			if sum1 - Sum in a:
				res = res + a[sum1 - Sum]
			if sum1 not in a:
				a[sum1] = 1
			else:
				a[sum1] = a[sum1] + 1
		return res


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		has = {}
		sum = 0
		count = 0
		has[0] = 1
		for i in range(n):
			sum += arr[i]
			val = sum - s
			if val in has:
				count += has[val]
			if sum not in has:
				has[sum] = 1
			else:
				has[sum] += 1
		return count
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	s = int(input())
	ob = Solution()
	print(ob.findSubarraySum(a, n, s))


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		cursum = 0
		d = {}
		cnt = 0
		for i in arr:
			cursum += i
			if cursum == Sum:
				cnt += 1
			if cursum - Sum in d:
				cnt += d[cursum - Sum]
			if cursum in d:
				d[cursum] += 1
			else:
				d[cursum] = 1
		return cnt
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	s = int(input())
	ob = Solution()
	print(ob.findSubarraySum(a, n, s))


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		pr = [0]
		s = 0
		for i in range(n):
			s += arr[i]
			pr.append(s)
		d = {}
		ans = 0
		for val in pr:
			ans += d.get(val - Sum, 0)
			d[val] = d.get(val, 0) + 1
		return ans
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	s = int(input())
	ob = Solution()
	print(ob.findSubarraySum(a, n, s))


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		ans = 0
		from collections import defaultdict
		dic = defaultdict(int)
		curr_sum = 0
		for i in arr:
			curr_sum += i
			ans += dic[curr_sum - Sum]
			dic[curr_sum] += 1
		return ans + dic[Sum]
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	s = int(input())
	ob = Solution()
	print(ob.findSubarraySum(a, n, s))


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		k = Sum
		drm = {}
		sm = 0
		rslt = 0
		for i in range(n):
			sm = sm + arr[i]
			if sm == k:
				rslt = rslt + 1
			if sm - k in drm.keys():
				rslt = rslt + drm[sm - k]
			if sm in drm.keys():
				drm[sm] = drm[sm] + 1
			else:
				drm[sm] = 1
		return rslt
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	s = int(input())
	ob = Solution()
	print(ob.findSubarraySum(a, n, s))


class Solution:

	def findSubarraySum(self, nums, n, k):
		d = dict()
		c = 0
		cou = 0
		d[0] = 1
		for i in range(len(nums)):
			c += nums[i]
			if c - k in d.keys():
				cou += d[c - k]
			if c not in d.keys():
				d[c] = 1
			else:
				d[c] += 1
		return cou
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	s = int(input())
	ob = Solution()
	print(ob.findSubarraySum(a, n, s))


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		m = {0: 1}
		cs = 0
		c = 0
		for i in range(n):
			cs += arr[i]
			if cs - Sum in m:
				c += m[cs - Sum]
			if cs in m:
				m[cs] += 1
			else:
				m[cs] = 1
		return c
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	s = int(input())
	ob = Solution()
	print(ob.findSubarraySum(a, n, s))


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		res = 0
		curSum = 0
		prefixSum = {0: 1}
		for i in arr:
			curSum += i
			diff = curSum - Sum
			res += prefixSum.get(diff, 0)
			prefixSum[curSum] = 1 + prefixSum.get(curSum, 0)
		return res


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		dict = {0: 1}
		s = 0
		count = 0
		for num in arr:
			s += num
			if s - Sum in dict:
				count += dict[s - Sum]
			if s in dict:
				dict[s] += 1
			else:
				dict[s] = 1
		return count


class Solution:

	def findSubarraySum(self, arr, n, k):
		cur = 0
		res = 0
		count = {0: 1}
		for i in range(n):
			cur += arr[i]
			res += count.get(cur - k, 0)
			count[cur] = count.get(cur, 0) + 1
		return res


class Solution:

	def findSubarraySum(self, arr, n, k):
		j = 0
		d = {}
		s = 0
		c = 0
		while j < n:
			s += arr[j]
			if s == k:
				c += 1
			if s - k in d:
				c += d[s - k]
				if s in d:
					d[s] += 1
				else:
					d[s] = 1
			elif s in d:
				d[s] += 1
			else:
				d[s] = 1
			j += 1
		return c


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		map = {}
		sumval = 0
		cnt = 0
		for i in range(n):
			sumval += arr[i]
			if sumval == Sum:
				cnt += 1
			if sumval - Sum in map:
				cnt += map[sumval - Sum]
			if sumval in map:
				map[sumval] += 1
			else:
				map[sumval] = 1
		return cnt


from collections import defaultdict

class Solution:

	def findSubarraySum(self, arr, n, Sum):
		c = 0
		d = defaultdict(int)
		d[0] = 1
		total = 0
		for i in range(n):
			total += arr[i]
			if total - Sum in d:
				c += d[total - Sum]
			d[total] += 1
		return c


class Solution:

	def findSubarraySum(self, nums, n, k):
		currSum = 0
		ansCount = 0
		prevSums = {0: 1}
		for num in nums:
			currSum += num
			if currSum - k in prevSums:
				ansCount += prevSums[currSum - k]
			if currSum in prevSums:
				prevSums[currSum] += 1
			else:
				prevSums[currSum] = 1
		return ansCount


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		d = dict()
		count = 0
		add = 0
		for i in range(n):
			add += arr[i]
			if add == Sum:
				count += 1
			if add - Sum in d:
				count += d[add - Sum]
			if add not in d:
				d[add] = 1
			else:
				d[add] += 1
		return count


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		store = {0: 1}
		sums = 0
		curr = 0
		for i in arr:
			sums += i
			if sums - Sum in store:
				curr += store[sums - Sum]
			if sums in store:
				store[sums] += 1
			else:
				store[sums] = 1
		return curr


from collections import defaultdict

class Solution:

	def findSubarraySum(self, arr, n, Sum):
		mp = defaultdict(lambda : 0)
		cur = 0
		count = 0
		for i in arr:
			cur += i
			if cur == Sum:
				count += 1
			if cur - Sum in mp.keys():
				count += mp[cur - Sum]
			mp[cur] += 1
		return count


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		dict_sum = {0: 1}
		num_of_subarrays = 0
		curr_sum = 0
		for i in range(0, n):
			curr_sum = curr_sum + arr[i]
			if curr_sum - Sum in dict_sum:
				num_of_subarrays += dict_sum[curr_sum - Sum]
			if curr_sum in dict_sum:
				dict_sum[curr_sum] += 1
			else:
				dict_sum[curr_sum] = 1
		return num_of_subarrays


class Solution:

	def findSubarraySum(self, arr, n, k):
		j = 0
		d = {}
		s = 0
		count = 0
		while j < len(arr):
			if s + arr[j] - k in d:
				count += len(d[s + arr[j] - k])
			s = s + arr[j]
			if s == k:
				count += 1
			if s in d:
				d[s].append(j)
			else:
				d[s] = [j]
			j += 1
		return count


class Solution:

	def findSubarraySum(self, arr, n, K):
		cs = 0
		ans = 0
		d = {}
		for i in range(n):
			cs += arr[i]
			if cs == K:
				ans += 1
			if cs - K in d:
				ans = ans + len(d[cs - K])
			if cs in d:
				d[cs].append(i)
			else:
				d[cs] = [i]
		return ans


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		count = 0
		currSum = 0
		sumDict = {}
		for i in range(n):
			currSum += arr[i]
			if currSum == Sum:
				count += 1
			if currSum - Sum in sumDict:
				count += sumDict[currSum - Sum]
			if currSum in sumDict:
				sumDict[currSum] += 1
			else:
				sumDict[currSum] = 1
		return count


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		(d, count) = ({}, 0)
		ps = 0
		for i in range(n):
			ps += arr[i]
			if ps == Sum:
				count += 1
			if ps - Sum in d:
				count += d[ps - Sum]
			if ps in d:
				d[ps] += 1
			if ps not in d:
				d[ps] = 1
		return count


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		mydict = {0: 1}
		summ = 0
		count = 0
		for i in arr:
			summ += i
			if summ - Sum in mydict:
				count += mydict[summ - Sum]
			if summ in mydict:
				mydict[summ] += 1
			else:
				mydict[summ] = 1
		return count


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		prefixHashMap = {0: 1}
		currSum = 0
		count = 0
		for a in arr:
			currSum += a
			diff = currSum - Sum
			count += prefixHashMap.get(diff, 0)
			prefixHashMap[currSum] = 1 + prefixHashMap.get(currSum, 0)
		return count


class Solution:

	def findSubarraySum(self, arr, n, sum):
		ans = 0
		map = {0: 1}
		currSum = 0
		for val in arr:
			currSum += val
			if currSum - sum in map:
				ans += map[currSum - sum]
			if currSum in map:
				map[currSum] += 1
			else:
				map[currSum] = 1
		return ans


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		hm = {}
		curr_sum = 0
		count = 0
		for i in range(n):
			curr_sum += arr[i]
			if curr_sum == Sum:
				count += 1
			if curr_sum - Sum in hm:
				count += hm[curr_sum - Sum]
			hm[curr_sum] = hm.get(curr_sum, 0) + 1
		return count


class Solution:

	def findSubarraySum(self, arr, n, k):
		prefix = []
		sum1 = 0
		for ele in arr:
			sum1 += ele
			prefix.append(sum1)
		count = 0
		res = {}
		for sums in prefix:
			if sums == k:
				count += 1
			if sums - k in res:
				count += res[sums - k]
			if sums in res:
				res[sums] += 1
			else:
				res[sums] = 1
		return count


class Solution:

	def findSubarraySum(self, arr, n, sum):
		count = 0
		su = 0
		dict = {}
		for i in range(n):
			su += arr[i]
			if su - sum == 0:
				count += 1
			if su - sum in dict:
				count += dict[su - sum]
			dict[su] = dict.get(su, 0) + 1
		return count


from collections import defaultdict

class Solution:

	def findSubarraySum(self, arr, n, Sum):
		count = 0
		s = 0
		d = dict()
		for i in range(n):
			s += arr[i]
			if s == Sum:
				count += 1
			if s - Sum in d:
				count += d[s - Sum]
			d[s] = d.get(s, 0) + 1
		return count


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		s = {0: 1}
		curr = 0
		ans = 0
		for i in arr:
			curr += i
			if curr - Sum in s:
				ans += s[curr - Sum]
			if curr in s:
				s[curr] += 1
			else:
				s[curr] = 1
		return ans


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		known_sums = {0: 1}
		current_sum = 0
		result = 0
		for elem in arr:
			current_sum += elem
			result += known_sums.get(current_sum - Sum, 0)
			if current_sum not in known_sums:
				known_sums[current_sum] = 1
			else:
				known_sums[current_sum] += 1
		return result


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		freq = {0: 1}
		_sum = 0
		cnt = 0
		for i in range(n):
			_sum += arr[i]
			if _sum - Sum in freq:
				cnt += freq[_sum - Sum]
			if _sum not in freq:
				freq[_sum] = 1
			else:
				freq[_sum] += 1
		return cnt


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		import collections
		d = collections.defaultdict(int)
		s = 0
		d[0] = 1
		counter = 0
		for i in arr:
			s += i
			temp = s - Sum
			counter += d[temp]
			d[s] += 1
		return counter


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		listed = {}
		listed[arr[0]] = 1
		if 0 in listed:
			listed[0] += 1
		else:
			listed[0] = 1
		ans = 0
		if arr[0] == Sum:
			ans += 1
		for i in range(1, n):
			arr[i] += arr[i - 1]
			x = arr[i] - Sum
			if x in listed:
				ans += listed[x]
			if arr[i] in listed:
				listed[arr[i]] += 1
			else:
				listed[arr[i]] = 1
		return ans


class Solution:

	def findSubarraySum(self, arr, N, K):
		ans = 0
		dct = dict()
		sm = 0
		for i in range(N):
			sm += arr[i]
			if sm in dct.keys():
				dct[sm] += 1
			else:
				dct[sm] = 1
			if K == sm:
				ans += 1
			if sm - K in dct.keys():
				ans += dct[sm - K]
		if K == 0:
			return ans - N
		return ans


from itertools import accumulate

class Solution:

	def findSubarraySum(self, arr, n, Sum):
		arr = list(accumulate(arr, lambda a, b: a + b))
		d = {}
		ans = 0
		for i in range(n):
			if arr[i] == Sum:
				ans += 1
			if arr[i] - Sum in d:
				ans += d[arr[i] - Sum]
			if arr[i] in d:
				d[arr[i]] += 1
			else:
				d[arr[i]] = 1
		return ans


class Solution:

	def findSubarraySum(self, arr, n, k):
		dic = {}
		dic[0] = 1
		pre = 0
		count = 0
		for i in range(n):
			pre += arr[i]
			if pre - k in dic:
				count += dic[pre - k]
			dic[pre] = dic.get(pre, 0) + 1
		return count


from collections import defaultdict

class Solution:

	def findSubarraySum(self, Arr, n, k):
		curr_su = 0
		c = 0
		d = defaultdict(lambda : 0)
		for i in Arr:
			curr_su += i
			if curr_su == k:
				c += 1
			if curr_su - k in d:
				c += d[curr_su - k]
			d[curr_su] += 1
		return c


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		current_sum = 0
		number_of_sub_arrays = 0
		map = {0: 1}
		for elements in arr:
			current_sum += elements
			if current_sum - Sum in map:
				number_of_sub_arrays += map[current_sum - Sum]
			if current_sum not in map:
				map[current_sum] = 1
			else:
				map[current_sum] += 1
		return number_of_sub_arrays


class Solution:

	def findSubarraySum(self, arr, n, Sum):
		Map = {}
		sum1 = 0
		c = 0
		for i in range(n):
			sum1 += arr[i]
			if sum1 == Sum:
				c += 1
			if sum1 - Sum in Map:
				c += Map[sum1 - Sum]
			if sum1 in Map:
				Map[sum1] += 1
			else:
				Map[sum1] = 1
		if c != 0:
			return c
		return 0


class Solution:

	def findSubarraySum(self, arr, n, target):
		count = 0
		hash_map = {}
		prefix_sum = 0
		for ele in arr:
			prefix_sum += ele
			if prefix_sum - target in hash_map:
				count += hash_map[prefix_sum - target]
			if prefix_sum == target:
				count += 1
			hash_map[prefix_sum] = hash_map.get(prefix_sum, 0) + 1
		return count


from collections import defaultdict

class Solution:

	def findSubarraySum(self, arr, n, Sum):
		d = defaultdict(lambda : 0)
		s = 0
		c = 0
		for i in range(0, n):
			s = s + arr[i]
			x = s - Sum
			if s == Sum:
				c += 1
			if d[x] > 0:
				c += d[x]
			d[s] += 1
		return c


class Solution:

	def findSubarraySum(self, arr, n, target):
		curr_sum = 0
		i = 0
		j = 0
		n = len(arr)
		sum_mapping = {}
		count = 0
		for i in range(n):
			curr_sum += arr[i]
			if curr_sum == target:
				count += 1
			if curr_sum - target in sum_mapping:
				count += sum_mapping[curr_sum - target]
			if curr_sum not in sum_mapping:
				sum_mapping[curr_sum] = 0
			sum_mapping[curr_sum] += 1
		return count