Given an unsorted array of integers and a sum. The task is to count the number of subarray which adds to the given sum.
Example 1:
Input:
n = 5
arr[] = {10,2,-2,-20,10}
sum = -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
arr[] = {1,4,20,3,10,5}
sum = 33
Output: 1
Explanation: Subarray with sum 33 is: 
[20,3,10].
Your Task:
This is a function problem. You only need to complete the function subArraySum() that takes arr, n, sum as parameters and returns the count of subarrays which adds up to the given sum. 
Expected Time Comlexity: O(n)
Expected Auxilary Space: O(n)
Constraints:
1 <= n <= 10^{5}
-10^{5} <= arr[i] <= 10^{5}
-10^{5} <= sum <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    
    #Complete this fuction
    #Function to count the number of subarrays which adds to the given sum.
    def subArraySum(self,arr, n, sum):
        #Your code here

Solutions:
class Solution:

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


class Solution:

	def subArraySum(self, arr, n, sum):
		import collections
		dict1 = {}
		sum_ = 0
		count = 0
		for i in range(n):
			if sum_ in dict1:
				dict1[sum_] = dict1[sum_] + 1
			else:
				dict1[sum_] = 1
			sum_ = sum_ + arr[i]
			if sum_ - sum in dict1:
				count = count + dict1[sum_ - sum]
		return count


class Solution:

	def subArraySum(self, arr, n, sum):
		hash = {}
		cnt = 0
		s = 0
		for el in arr:
			s += el
			if s == sum:
				cnt += 1
			cnt += hash.get(s - sum, 0)
			hash[s] = hash.get(s, 0) + 1
		return cnt


from collections import OrderedDict

class Solution:

	def subArraySum(self, arr, n, sum):
		mp = OrderedDict({})
		pre_sum = 0
		count = 0
		for i in range(n):
			pre_sum += arr[i]
			if pre_sum == sum:
				count += 1
			x = mp.get(pre_sum - sum, False)
			if x is not False:
				count += x
			mp[pre_sum] = mp.get(pre_sum, 0) + 1
		return count


class Solution:

	def subArraySum(self, arr, n, sum):
		mydict = {0: 1}
		sum1 = 0
		c = 0
		for i in arr:
			sum1 += i
			if sum1 - sum in mydict:
				c += mydict[sum1 - sum]
			if sum1 in mydict:
				mydict[sum1] += 1
			else:
				mydict[sum1] = 1
		return c


class Solution:

	def subArraySum(self, arr, n, sum):
		d = {}
		pre_sum = 0
		count = 0
		for i in range(n):
			pre_sum += arr[i]
			x = pre_sum - sum
			if x in d:
				count += d[x]
			if pre_sum == sum:
				count += 1
			else:
				pass
			if pre_sum in d:
				d[pre_sum] += 1
			else:
				d[pre_sum] = 1
		return count


class Solution:

	def subArraySum(self, arr, n, sum):
		count = 0
		csum = 0
		hmap = {}
		for val in arr:
			csum += val
			if csum == sum:
				count += 1
			if csum - sum in hmap:
				count += hmap[csum - sum]
			hmap[csum] = hmap.get(csum, 0) + 1
		return count


class Solution:

	def subArraySum(self, arr, n, sum):
		prefix_sum = {0: 1}
		curr_sum = 0
		count = 0
		for i in range(n):
			curr_sum += arr[i]
			if curr_sum - sum in prefix_sum:
				count += prefix_sum[curr_sum - sum]
			if curr_sum in prefix_sum:
				prefix_sum[curr_sum] += 1
			else:
				prefix_sum[curr_sum] = 1
		return count


from collections import defaultdict

class Solution:

	def subArraySum(self, arr, n, target):
		store = defaultdict(lambda : 0)
		store[0] += 1
		output = 0
		summa = 0
		for item in arr:
			summa += item
			output += store[summa - target]
			store[summa] += 1
		return output


class Solution:

	def subArraySum(self, arr, n, sum):
		freq = {}
		presum = 0
		freq[presum] = 1
		c = 0
		for i in arr:
			presum += i
			if presum - sum in freq:
				c += freq[presum - sum]
			if presum not in freq:
				freq[presum] = 0
			freq[presum] += 1
		return c


class Solution:

	def subArraySum(self, arr, n, sum):
		aux = []
		aux.append(0)
		d = {}
		s = 0
		c = 0
		d[0] = 1
		for i in range(n):
			a = arr[i]
			s = s + a
			y = s - sum
			if y in d:
				freq = d[y]
				c = c + freq
			if s not in d:
				d[s] = 1
			else:
				d[s] = d[s] + 1
		return c


class Solution:

	def subArraySum(self, arr, n, sum):
		dict = {0: 1}
		temp = 0
		c = 0
		for i in arr:
			temp += i
			if temp - sum in dict:
				c += dict[temp - sum]
			if temp in dict:
				dict[temp] += 1
			else:
				dict[temp] = 1
		return c


class Solution:

	def subArraySum(self, arr, n, sum):
		d = {0: 1}
		curr_sum = 0
		ans = 0
		for i in arr:
			curr_sum += i
			k = curr_sum - sum
			if k in d:
				ans += d[k]
			if curr_sum in d:
				d[curr_sum] += 1
			else:
				d[curr_sum] = 1
		return ans


class Solution:

	def subArraySum(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 subArraySum(self, arr, n, sum):
		d = {}
		s = 0
		l = []
		for i in arr:
			s += i
			l.append(s)
		ans = 0
		for i in l:
			if i == sum:
				ans += 1
			if i - sum in d:
				ans += d[i - sum]
			try:
				d[i] += 1
			except:
				d[i] = 1
		return ans


class Solution:

	def subArraySum(self, arr, n, S):
		d = {}
		(a, d[0]) = (0, 1)
		c = 0
		for i in range(n):
			a += arr[i]
			if a - S in d:
				c += d[a - S]
			if a not in d:
				d[a] = 1
			else:
				d[a] += 1
		return c


class Solution:

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


from collections import defaultdict

class Solution:

	def subArraySum(self, arr, n, sum):
		mp = defaultdict(int)
		subs = 0
		pref = 0
		mp[0] = 1
		for i in range(n):
			pref += arr[i]
			subs += mp[pref - sum]
			mp[pref] += 1
		return subs


class Solution:

	def subArraySum(self, arr, n, s):
		m = {}
		m[0] = 1
		sum = 0
		cnt = 0
		for i in range(n):
			sum += arr[i]
			if sum - s in m:
				cnt += m[sum - s]
			if sum not in m:
				m[sum] = 1
			else:
				m[sum] += 1
		return cnt


class Solution:

	def subArraySum(self, arr, n, sum):
		dic = {}
		sums = 0
		c = 0
		for i in range(n):
			sums += arr[i]
			if sums == sum:
				c += 1
			if sums - sum in dic:
				c += dic[sums - sum]
			if sums in dic:
				dic[sums] += 1
			else:
				dic[sums] = 1
		return c


class Solution:

	def subArraySum(self, arr, n, x):
		hold = {}
		curr_sum = 0
		res = 0
		for num in arr:
			curr_sum += num
			if curr_sum == x:
				res += 1
			rem = curr_sum - x
			if rem in hold:
				res += hold[rem]
			if curr_sum in hold:
				hold[curr_sum] += 1
			else:
				hold[curr_sum] = 1
		return res


class Solution:

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


class Solution:

	def subArraySum(self, arr, n, sum):
		f = {0: 1}
		pre = 0
		c = 0
		for i in arr:
			pre += i
			if pre - sum in f:
				c += f[pre - sum]
			if pre in f:
				f[pre] += 1
			else:
				f[pre] = 1
		return c


class Solution:

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


class Solution:

	def subArraySum(self, arr, n, sum):
		d = {}
		cnt = 0
		prefix = [0 for i in range(n)]
		prefix[0] = arr[0]
		d[prefix[0]] = 1
		if sum == prefix[0]:
			cnt += 1
		for i in range(1, n):
			prefix[i] = prefix[i - 1] + arr[i]
			if prefix[i] - sum in d:
				cnt += d[prefix[i] - sum]
			if prefix[i] == sum:
				cnt += 1
			d[prefix[i]] = d.get(prefix[i], 0) + 1
		return cnt


from collections import defaultdict

class Solution:

	def subArraySum(self, arr, n, target):
		psum = defaultdict(int)
		tcounts = 0
		rsum = 0
		for num in arr:
			rsum += num
			diff = rsum - target
			if rsum == target:
				tcounts += 1
			if psum[diff] > 0:
				tcounts += psum[diff]
			psum[rsum] += 1
		return tcounts


class Solution:

	def subArraySum(self, arr, n, sum):
		cumMap = dict()
		curr = 0
		count = 0
		for i in range(n):
			curr += arr[i]
			if curr == sum:
				count += 1
			if curr - sum in cumMap:
				count += cumMap[curr - sum]
			cumMap[curr] = cumMap.get(curr, 0) + 1
		return count


class Solution:

	def subArraySum(self, arr, n, sum):
		cumMap = dict()
		curr = 0
		count = 0
		for i in range(n):
			curr += arr[i]
			if curr == sum:
				count += 1
			if curr - sum in cumMap:
				count += len(cumMap[curr - sum])
			if curr in cumMap:
				cumMap[curr].append(i)
			else:
				cumMap[curr] = [i]
		return count


class Solution:

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


class Solution:

	def subArraySum(self, arr, n, sum):
		d = {0: 1}
		s = 0
		ans = 0
		for a in arr:
			s += a
			c = s - sum
			if c in d:
				ans += d[c]
			d[s] = 1 + d.get(s, 0)
		return ans


class Solution:

	def subArraySum(self, arr, n, sum):
		d = {0: 1}
		pre_sum = 0
		c = 0
		for item in arr:
			pre_sum += item
			target = pre_sum - sum
			if target in d:
				c += d[target]
			if pre_sum in d:
				d[pre_sum] += 1
			else:
				d[pre_sum] = 1
		return c


from collections import defaultdict

class Solution:

	def subArraySum(self, arr, n, sum):
		total = 0
		count = 0
		d = defaultdict(list)
		for i in range(n):
			total += arr[i]
			if total == sum:
				count += 1
			if total - sum in d:
				count += len(d[total - sum])
			d[total].append(i)
		return count


class Solution:

	def subArraySum(self, arr, n, sum):
		sums = dict({0: 1})
		curr_sum = 0
		count = 0
		for i in arr:
			curr_sum += i
			if curr_sum - sum in sums:
				count += sums[curr_sum - sum]
			if curr_sum in sums:
				sums[curr_sum] += 1
			else:
				sums[curr_sum] = 1
		return count


class Solution:

	def subArraySum(self, arr, n, sum):
		d = dict()
		presum = 0
		count = 0
		for x in arr:
			presum += x
			if presum == sum:
				count += 1
			if presum - sum in d:
				count += d[presum - sum]
			d[presum] = d.get(presum, 0) + 1
		return count


class Solution:

	def subArraySum(self, arr, n, sum):
		hash = {}
		prefix_sum = 0
		ans = 0
		for i in range(n):
			prefix_sum += arr[i]
			if prefix_sum == sum:
				ans += 1
			if prefix_sum - sum in hash:
				ans += hash[prefix_sum - sum]
			if prefix_sum in hash:
				hash[prefix_sum] += 1
			else:
				hash[prefix_sum] = 1
		return ans


class Solution:

	def subArraySum(self, arr, n, sum):
		d = {0: 1}
		currsum = 0
		count = 0
		for i in range(n):
			currsum += arr[i]
			count += d.get(currsum - sum, 0)
			d[currsum] = 1 + d.get(currsum, 0)
		return count


from collections import defaultdict

class Solution:

	def subArraySum(self, arr, n, sum):
		store = defaultdict(lambda : 0)
		presum = 0
		ans = 0
		for num in arr:
			presum += num
			if presum == sum:
				ans += 1
			if presum - sum in store:
				ans += store[presum - sum]
			store[presum] += 1
		return ans


class Solution:

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


class Solution:

	def subArraySum(self, arr, n, sum1):
		if arr[0] == sum1:
			count = 1
		else:
			count = 0
		prefix_sum = arr[0]
		prefix_sum_dict = {}
		prefix_sum_dict[arr[0]] = 1
		for i in range(1, n):
			prefix_sum += arr[i]
			if prefix_sum == sum1:
				count += 1
			if prefix_sum_dict.get(prefix_sum - sum1):
				count += prefix_sum_dict.get(prefix_sum - sum1)
			prefix_sum_dict[prefix_sum] = prefix_sum_dict.get(prefix_sum, 0) + 1
		return count


class Solution:

	def subArraySum(self, arr, n, sum):
		c = 0
		summ = 0
		d = {}
		for val in arr:
			summ += val
			if summ == sum:
				c += 1
			if summ - sum in d:
				c += d[summ - sum]
			d[summ] = 1 + d.get(summ, 0)
		return c


class Solution:

	def subArraySum(self, arr, n, sum):
		hash = dict()
		totalsum = 0
		count = 0
		for i in range(n):
			totalsum += arr[i]
			num = totalsum - sum
			if totalsum == sum:
				count += 1
			if hash.get(num, 0) != 0:
				count += hash.get(num)
			hash[totalsum] = hash.get(totalsum, 0) + 1
		return count


from collections import defaultdict

class Solution:

	def subArraySum(self, arr, n, s):
		d = defaultdict(int)
		d[0] = 1
		t = res = 0
		for x in arr:
			t += x
			res += d[t - s]
			d[t] += 1
		return res


class Solution:

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


class Solution:

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


class Solution:

	def subArraySum(self, arr, n, summ):
		sumRec = {0: 1}
		res = 0
		sumSF = 0
		for i in range(n):
			sumSF += arr[i]
			if sumSF - summ in sumRec:
				res += sumRec[sumSF - summ]
			if sumSF in sumRec:
				sumRec[sumSF] += 1
			else:
				sumRec[sumSF] = 1
		return res


from collections import defaultdict

class Solution:

	def subArraySum(self, A, n, sum):
		sum_already_present = defaultdict(int)
		curr_sum = 0
		ans = 0
		for num in A:
			curr_sum += num
			if curr_sum == sum:
				ans += 1
			if curr_sum - sum in sum_already_present:
				ans += sum_already_present[curr_sum - sum]
			sum_already_present[curr_sum] += 1
		return ans


class Solution:

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


def sub_s_sum_count(a, s):
	prefix_sums = {}
	prefix = 0
	c = 0
	for i in a:
		prefix += i
		if prefix == s:
			c += 1
		if prefix - s in prefix_sums:
			c += prefix_sums[prefix - s]
		if prefix in prefix_sums:
			prefix_sums[prefix] += 1
		else:
			prefix_sums[prefix] = 1
	return c

class Solution:

	def subArraySum(self, arr, n, sum):
		return sub_s_sum_count(arr, sum)


class Solution:

	def subArraySum(self, arr, n, sum):
		x = {}
		pre_sum = 0
		count = 0
		for i in range(len(arr)):
			pre_sum += arr[i]
			if pre_sum - sum in x:
				val = x[pre_sum - sum]
				count += x[pre_sum - sum]
			if pre_sum not in x:
				x[pre_sum] = 1
			else:
				x[pre_sum] += 1
			if pre_sum == sum:
				count += 1
		return count


class Solution:

	def subArraySum(self, nums, n, k):
		(cnt, total) = (0, 0)
		cache = {0: 1}
		for v in nums:
			total += v
			if cache.get(total - k):
				cnt += cache[total - k]
			if cache.get(total):
				cache[total] += 1
			else:
				cache[total] = 1
		return cnt


class Solution:

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


class Solution:

	def subArraySum(self, arr, n, sum):
		d = {0: 1}
		s = 0
		r = 0
		for x in arr:
			s += x
			if s - sum in d:
				r += d[s - sum]
			d[s] = d.setdefault(s, 0) + 1
		return r


class Solution:

	def subArraySum(self, arr, n, sum):
		dct = dict()
		dct[0] = 1
		prefix = 0
		count = 0
		for i in arr:
			prefix += i
			if prefix - sum in dct:
				count += dct[prefix - sum]
			if prefix in dct:
				dct[prefix] += 1
			else:
				dct[prefix] = 1
		return count


class Solution:

	def subArraySum(self, arr, n, sum):
		ans = 0
		prefsum = 0
		d = {0: 1}
		for num in arr:
			prefsum = prefsum + num
			if prefsum - sum in d:
				ans = ans + d[prefsum - sum]
			if prefsum not in d:
				d[prefsum] = 1
			else:
				d[prefsum] = d[prefsum] + 1
		return ans


class Solution:

	def subArraySum(self, arr, n, sum):
		di = {0: 1}
		(lsum, psum) = (0, 0)
		for i in arr:
			psum += i
			if psum - sum in di:
				lsum += di[psum - sum]
			if psum in di:
				di[psum] += 1
			else:
				di[psum] = 1
		return lsum


class Solution:

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


class Solution:

	def subArraySum(self, arr, n, sum):
		cursum = 0
		count = 0
		prefixMap = {}
		for num in arr:
			cursum += num
			if cursum == sum:
				count += 1
			if cursum - sum in prefixMap:
				count += prefixMap[cursum - sum]
			prefixMap[cursum] = prefixMap.get(cursum, 0) + 1
		return count