Given an unsorted array of integers, find the number of continuous subarrays having sum exactly equal to a given number k.
Example 1:
Input:
N = 5
Arr = {10 , 2, -2, -20, 10}
k = -10
Output: 3
Explaination: 
Subarrays: arr[0...3], arr[1...4], arr[3..4]
have sum exactly equal to -10.
Example 2:
Input:
N = 6
Arr = {9, 4, 20, 3, 10, 5}
k = 33
Output: 2
Explaination: 
Subarrays : arr[0...2], arr[2...4] have sum
exactly equal to 33.
Your Task:
You don't need to read input or print anything. Your task is to complete the function findSubArraySum() which takes the array Arr[] and its size N and k as input parameters and returns the count of subarrays.
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 2*10^{4}
-10^{3} ≤ Arr[i] ≤ 10^{3}
-10^{7} ≤ k ≤ 10^{7}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def findSubArraySum(self, Arr, N, k):
        # code here

Solutions:
from collections import defaultdict

class Solution:

	def findSubArraySum(self, Arr, N, k):
		default = {}
		res = 0
		cur = 0
		for i in Arr:
			cur += i
			if cur == k:
				res += 1
			if cur - k in default:
				res += default[cur - k]
			if cur in default:
				default[cur] += 1
			else:
				default[cur] = 1
		return res


class Solution:

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


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


class Solution:

	def findSubArraySum(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


class Solution:

	def findSubArraySum(self, Arr, N, k):
		mp = dict()
		mp[0] = 1
		run_sum = 0
		cnt = 0
		for i in range(0, N):
			run_sum = run_sum + Arr[i]
			if mp.get(run_sum - k, 0) != 0:
				cnt += mp[run_sum - k]
			mp[run_sum] = mp.get(run_sum, 0) + 1
		return cnt


class Solution:

	def findSubArraySum(self, Arr, N, k):
		hmap = {}
		su = 0
		count = 0
		for i in range(N):
			su += Arr[i]
			if su == k:
				count += 1
			if su - k in hmap:
				count += hmap[su - k]
			if su in hmap:
				hmap[su] += 1
			else:
				hmap[su] = 1
		return count


from collections import defaultdict

class Solution:

	def findSubArraySum(self, Arr, N, k):
		hashmap = defaultdict(int)
		nums = Arr
		result = 0
		cursum = 0
		for each in nums:
			cursum += each
			if cursum == k:
				result += 1
			if cursum - k in hashmap:
				result += hashmap[cursum - k]
			hashmap[cursum] += 1
		return result


{0: 1, 1: 1, -6: 1, -2: 1}

class Solution:

	def findSubArraySum(self, Arr, N, k):
		pref_sum = {0: 1}
		(curr_sum, res) = (0, 0)
		for i in range(len(Arr)):
			curr_sum += Arr[i]
			if curr_sum - k in pref_sum:
				res += pref_sum[curr_sum - k]
			if curr_sum in pref_sum:
				pref_sum[curr_sum] += 1
			if curr_sum not in pref_sum:
				pref_sum[curr_sum] = 1
		return res


class Solution:

	def findSubArraySum(self, Arr, N, k):
		(res, curSum) = (0, 0)
		prefixSums = {0: 1}
		for num in Arr:
			curSum += num
			diff = curSum - k
			res += prefixSums.get(diff, 0)
			prefixSums[curSum] = 1 + prefixSums.get(curSum, 0)
		return res


class Solution:

	def findSubArraySum(self, arr, N, k):
		count = 0
		hashmap = {}
		currsum = 0
		for i in arr:
			currsum += i
			if currsum == k:
				count += 1
			if currsum - k in hashmap:
				count += hashmap[currsum - k]
			if currsum in hashmap:
				hashmap[currsum] += 1
			else:
				hashmap[currsum] = 1
		return count


from collections import defaultdict

class Solution:

	def findSubArraySum(self, Arr, N, k):
		(res, s) = (0, 0)
		d = defaultdict(int)
		for i in range(N):
			s += Arr[i]
			if s == k:
				res += 1
			res += d[s - k]
			d[s] += 1
		return res


class Solution:

	def findSubArraySum(self, Arr, N, k):
		sum_var = 0
		sum_dict = {}
		answer = 0
		for num in Arr:
			sum_var += num
			if sum_var - k in sum_dict:
				answer += sum_dict[sum_var - k]
			if sum_var == k:
				answer += 1
			if sum_var in sum_dict:
				sum_dict[sum_var] += 1
			else:
				sum_dict[sum_var] = 1
		return answer


from collections import defaultdict

class Solution:

	def findSubArraySum(self, nums, N, k):
		currSum = 0
		prevSums = defaultdict(lambda : 0)
		max_ = 0
		for num in nums:
			currSum += num
			if currSum == k:
				max_ += 1
			if currSum - k in prevSums:
				max_ += prevSums[currSum - k]
			prevSums[currSum] += 1
		return max_


from collections import defaultdict

class Solution:

	def findSubArraySum(self, Arr, N, k):
		sum = 0
		count = 0
		default = defaultdict(lambda : 0)
		for i in range(N):
			sum = sum + Arr[i]
			if sum == k:
				count = count + 1
			if sum - k in default:
				count += default[sum - k]
			default[sum] += 1
		return count


class Solution:

	def findSubArraySum(self, Arr, N, k):
		dic = {}
		(c, cnt) = (0, 0)
		for i in Arr:
			c += i
			if c == k:
				cnt += 1
			if c - k in dic:
				cnt += dic[c - k]
			if c in dic:
				dic[c] += 1
			else:
				dic[c] = 1
		return cnt


class Solution:

	def findSubArraySum(self, Arr, N, k):
		a = Arr
		n = N
		count = 0
		s = 0
		di = {}
		for i in range(n):
			s += a[i]
			if s == k:
				count += 1
			if s in di:
				di[s] += 1
			else:
				di[s] = 1
			if s - k in di:
				count += di[s - k]
		return count


class Solution:

	def findSubArraySum(self, Arr, N, k):
		hm = {0: 1}
		hm[0] = 1
		ps = 0
		count_subarr = 0
		for i in range(len(Arr)):
			ps += Arr[i]
			if ps - k in hm:
				count_subarr += hm[ps - k]
			if ps in hm:
				hm[ps] += 1
			else:
				hm[ps] = 1
		return count_subarr


class Solution:

	def findSubArraySum(self, Arr, N, k):
		result = 0
		currentSum = 0
		prefixSums = {0: 1}
		for n in Arr:
			currentSum += n
			difference = currentSum - k
			result += prefixSums.get(difference, 0)
			prefixSums[currentSum] = prefixSums.get(currentSum, 0) + 1
		return result


class Solution:

	def findSubArraySum(self, arr, N, k):
		dic = dict()
		summ = 0
		count = 0
		for i in range(N):
			summ += arr[i]
			if summ == k:
				count += 1
			more = summ - k
			if more in dic:
				count += dic[more]
			if summ in dic:
				dic[summ] += 1
			else:
				dic[summ] = 1
		return count


class Solution:

	def findSubArraySum(self, Arr, N, k):
		count = 0
		sum = 0
		h = {0: 1}
		for x in Arr:
			sum += x
			count += h.get(sum - k, 0)
			h[sum] = h.get(sum, 0) + 1
		return count


class Solution:

	def findSubArraySum(self, Arr, N, k):
		ans = 0
		add = 0
		dic = {}
		dic[0] = 1
		for i in Arr:
			add += i
			if add - k in dic:
				ans += dic[add - k]
			dic[add] = dic.get(add, 0) + 1
		return ans


class Solution:

	def findSubArraySum(self, Arr, N, k):
		dict = {}
		dict[0] = 1
		(s, c) = (0, 0)
		for i in Arr:
			s += i
			if s - k in dict:
				c += dict[s - k]
			if s in dict:
				dict[s] += 1
			else:
				dict[s] = 1
		return c


class Solution:

	def findSubArraySum(self, nums, n, k):
		prefixSum = 0
		count = 0
		d = {0: 1}
		for i in range(0, len(nums)):
			prefixSum += nums[i]
			remove = prefixSum - k
			if remove in d:
				count += d[remove]
			if prefixSum not in d:
				d[prefixSum] = 1
			else:
				d[prefixSum] += 1
		return count


class Solution:

	def findSubArraySum(self, arr, N, k):
		s = {}
		s[0] = 1
		su = 0
		c = 0
		for i in arr:
			su += i
			if su - k in s:
				c += s[su - k]
			if su not in s:
				s[su] = 0
			s[su] += 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, k):
		res = 0
		currSum = 0
		prefixSum = {0: 1}
		for num in Arr:
			currSum += num
			diff = currSum - k
			res = res + prefixSum.get(diff, 0)
			prefixSum[currSum] = 1 + prefixSum.get(currSum, 0)
		return res


class Solution:

	def findSubArraySum(self, Arr, N, k):
		m = {}
		m[0] = 1
		prefix = 0
		ans = 0
		for a in Arr:
			prefix += a
			if prefix - k in m:
				ans += m[prefix - k]
			m[prefix] = m.get(prefix, 0) + 1
		return ans


class Solution:

	def findSubArraySum(self, Arr, N, k):
		h = {}
		sum = 0
		c = 0
		for i in Arr:
			sum = sum + i
			if sum not in h:
				h[sum] = 1
			else:
				h[sum] += 1
			if sum == k:
				c += 1
			if sum - k in h.keys():
				c += h[sum - k]
		return c


class Solution:

	def findSubArraySum(self, Arr, N, k):
		pre_sum = 0
		count = 0
		my_dict = {}
		for value in Arr:
			pre_sum += value
			if pre_sum == k:
				count += 1
			if pre_sum - k in my_dict:
				count += my_dict[pre_sum - k]
			my_dict[pre_sum] = my_dict.get(pre_sum, 0) + 1
		return count


class Solution:

	def findSubArraySum(self, Arr, N, k):
		count = 0
		preSum = 0
		h = {}
		h[0] = 1
		for i in range(N):
			preSum += Arr[i]
			rem = preSum - k
			if rem in h:
				count += h[rem]
			h[preSum] = h.get(preSum, 0) + 1
		return count


class Solution:

	def findSubArraySum(self, Arr, N, k):
		nums = Arr
		hm = dict()
		result = 0
		curr_sum = 0
		for val in nums:
			curr_sum += val
			if curr_sum == k:
				result += 1
			if curr_sum - k in hm:
				result += hm[curr_sum - k]
			hm[curr_sum] = hm.get(curr_sum, 0) + 1
		return result


class Solution:

	def findSubArraySum(self, arr, N, k):
		mp = {}
		cnt = 0
		summ = 0
		for (ind, val) in enumerate(arr):
			summ = summ + val
			if summ == k:
				cnt = cnt + 1
			if summ - k in mp:
				cnt = cnt + mp[summ - k]
			if summ not in mp:
				mp[summ] = 1
			else:
				mp[summ] += 1
		return cnt


class Solution:

	def findSubArraySum(self, Arr, N, k):
		c = {}
		c[0] = 1
		total = 0
		cur_sum = 0
		for num in Arr:
			cur_sum += num
			if cur_sum - k in c:
				total += c[cur_sum - k]
			if cur_sum in c:
				c[cur_sum] += 1
			else:
				c[cur_sum] = 1
		return total


class Solution:

	def findAllSubArrays(self, arr, k):
		Count = 0
		prefixSum = 0
		hasmap = {}
		hasmap[0] = 1
		for i in range(len(arr)):
			prefixSum += arr[i]
			removalValues = prefixSum - k
			if removalValues in hasmap:
				Count += hasmap[removalValues]
			if prefixSum in hasmap:
				hasmap[prefixSum] += 1
			else:
				hasmap[prefixSum] = 1
		return Count

	def findSubArraySum(self, Arr, N, k):
		return self.findAllSubArrays(Arr, k)


class Solution:

	def findSubArraySum(self, arr, N, k):
		dic = {}
		s = 0
		ans = 0
		for i in range(N):
			s += arr[i]
			if s == k:
				ans += 1
			if s - k in dic:
				ans += dic[s - k]
			if s in dic:
				dic[s] += 1
			else:
				dic[s] = 1
		return ans


class Solution:

	def findSubArraySum(self, arr, N, k):
		freq = {0: 1}
		TotalSum = 0
		count = 0
		for i in arr:
			TotalSum += i
			if TotalSum - k in freq:
				count += freq[TotalSum - k]
			if TotalSum in freq:
				freq[TotalSum] += 1
			else:
				freq[TotalSum] = 1
		return count


class Solution:

	def findSubArraySum(self, arr, n, k):
		ans = 0
		dic = {0: 1}
		sm = 0
		for el in arr:
			sm += el
			if sm - k in dic:
				ans += dic[sm - k]
			if sm in dic:
				dic[sm] += 1
			else:
				dic[sm] = 1
		return ans


class Solution:

	def findSubArraySum(self, arr, N, k):
		map = {}
		map[0] = 1
		(preSum, count) = (0, 0)
		for i in range(N):
			preSum += arr[i]
			remove = preSum - k
			count += map.get(remove, 0)
			map[preSum] = map.get(preSum, 0) + 1
		return count


class Solution:

	def findSubArraySum(self, Arr, N, k):
		d = {0: 1}
		su = 0
		c = 0
		for i in Arr:
			su += i
			if su - k in d:
				c += d[su - k]
			d[su] = d.get(su, 0) + 1
		return c


from collections import defaultdict

class Solution:

	def findSubArraySum(self, Arr, N, k):
		(summ, data) = (0, defaultdict(lambda : 0))
		res = 0
		for each in Arr:
			summ += each
			if summ == k:
				res += 1
			req = summ - k
			if req in data:
				res += data[req]
			data[summ] += 1
		return res


from collections import defaultdict

class Solution:

	def findSubArraySum(self, Arr, N, k):
		Dict = defaultdict(int)
		Dict[0] = 1
		curr_sum = 0
		res = 0
		for i in range(len(Arr)):
			curr_sum += Arr[i]
			if curr_sum - k in Dict:
				res += Dict[curr_sum - k]
			Dict[curr_sum] += 1
		return res


class Solution:

	def findSubArraySum(self, A, N, k):
		prefix_sum = {}
		sol = 0
		curr_sum = 0
		for i in range(N):
			curr_sum += A[i]
			if curr_sum in prefix_sum:
				prefix_sum[curr_sum] += 1
			else:
				prefix_sum[curr_sum] = 1
			if curr_sum == k:
				sol += 1
			if curr_sum - k in prefix_sum:
				sol += prefix_sum[curr_sum - k]
		return sol


from collections import *

class Solution:

	def findSubArraySum(self, a, n, k):
		j = 0
		sm = 0
		d = defaultdict(int)
		ans = 0
		for i in range(n):
			sm += a[i]
			if sm == k:
				ans += 1
			d[sm] += 1
			ans += d[sm - k]
		return ans


class Solution:

	def findSubArraySum(self, arr, N, k):
		d = {}
		c = 0
		ans = 0
		for i in arr:
			c = c + i
			d[c] = d.get(c, 0) + 1
			if c - k in d:
				ans += d[c - k]
			if c == k:
				ans += 1
		return ans


class Solution:

	def findSubArraySum(self, Arr, N, k):
		m = {}
		m[0] = 1
		curr = 0
		ans = 0
		for i in Arr:
			curr += i
			if curr - k in m:
				ans += m[curr - k]
			m[curr] = m.get(curr, 0) + 1
		return ans


from collections import defaultdict

class Solution:

	def findSubArraySum(self, Arr, N, k):
		mappy = defaultdict(int)
		ans = 0
		cursum = 0
		for i in range(N):
			cursum += Arr[i]
			if cursum == k:
				ans += 1
			if cursum - k in mappy:
				ans += mappy[cursum - k]
			mappy[cursum] += 1
		return ans


class Solution:

	def findSubArraySum(self, arr, N, k):
		co = 0
		sum1 = 0
		dic = {}
		for i in range(len(arr)):
			sum1 += arr[i]
			if sum1 == k:
				co += 1
			if sum1 in dic:
				dic[sum1] += 1
			else:
				dic[sum1] = 1
			co += dic.get(sum1 - k, 0)
		return co


class Solution:

	def findSubArraySum(self, Arr, N, k):
		h = {0: 1}
		temp = 0
		ans = 0
		for i in range(N):
			temp = temp + Arr[i]
			if temp not in h:
				h[temp] = 1
			else:
				h[temp] += 1
			if temp - k in h:
				ans += h[temp - k]
		return ans


class Solution:

	def findSubArraySum(self, Arr, N, k):
		count = 0
		d = {}
		sum = 0
		for (i, v) in enumerate(Arr):
			sum += v
			if sum == k:
				count += 1
			rem = sum - k
			if rem in d:
				count += d[rem]
			if sum in d:
				d[sum] += 1
			else:
				d[sum] = 1
		return count


class Solution:

	def findSubArraySum(self, arr, N, k):
		d = {}
		count = 0
		sum = 0
		for i in range(0, N):
			sum += arr[i]
			if sum == k:
				count += 1
			if sum - k in d:
				count += d[sum - k]
			if sum in d:
				d[sum] += 1
			else:
				d[sum] = 1
		return count


from collections import defaultdict

class Solution:

	def findSubArraySum(self, Arr, N, k):
		pre = defaultdict(int)
		s = c = 0
		for i in Arr:
			s += i
			if s == k:
				c += 1
			if s - k in pre:
				c += pre[s - k]
			pre[s] += 1
		return c


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, k):
		pref_arr = 0
		(mp, c) = ({}, 0)
		for (i, val) in enumerate(Arr):
			pref_arr += val
			if pref_arr == k:
				c += 1
			if pref_arr - k in mp:
				c += mp[pref_arr - k]
			if pref_arr in mp:
				mp[pref_arr] += 1
			else:
				mp[pref_arr] = 1
		return c


from collections import defaultdict

class Solution:

	def findSubArraySum(self, Arr, N, k):
		currsum = 0
		count = 0
		d = defaultdict(int)
		for i in range(N):
			currsum += Arr[i]
			if currsum == k:
				count += 1
			if currsum - k in d:
				count += d[currsum - k]
			d[currsum] += 1
		return count


class Solution:

	def findSubArraySum(self, a, n, k):
		d = {}
		prefsum = 0
		res = 0
		for i in range(n):
			prefsum += a[i]
			if prefsum == k:
				res += 1
			if prefsum not in d:
				d[prefsum] = 1
			else:
				d[prefsum] += 1
			if prefsum - k in d:
				res += d[prefsum - k]
		return res


class Solution:

	def findSubArraySum(self, Arr, N, k):
		hashmap = {0: 1}
		summ = 0
		count = 0
		for i in range(N):
			summ += Arr[i]
			if summ - k in hashmap:
				count += hashmap[summ - k]
			hashmap[summ] = 1 if summ not in hashmap else hashmap[summ] + 1
		return count


class Solution:

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


class Solution:

	def findSubArraySum(self, Arr, N, k):
		dic = {}
		sum = 0
		count = 0
		for i in range(N):
			sum = sum + Arr[i]
			if sum == k:
				count += 1
			if sum - k in dic:
				count += dic[sum - k]
			dic[sum] = dic.get(sum, 0) + 1
		return count


class Solution:

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


from collections import defaultdict

class Solution:

	def findSubArraySum(self, arr, n, k):
		res = 0
		previous_sums = defaultdict(int)
		sum = 0
		for num in arr:
			sum += num
			if sum == k:
				res += 1
			if sum - k in previous_sums:
				res += previous_sums[sum - k]
			previous_sums[sum] += 1
		return res


class Solution:

	def findSubArraySum(self, Arr, N, k):
		s = 0
		count = 0
		d = {}
		d[0] = 1
		for i in range(N):
			s = s + Arr[i]
			if s - k in d:
				count += d[s - k]
			if s in d:
				d[s] += 1
			else:
				d[s] = 1
		return count


from collections import defaultdict as dd

class Solution:

	def findSubArraySum(self, a1, n, k):
		c1 = dd(list)
		s1 = 0
		ans = []
		for i in range(n):
			s1 += a1[i]
			c1[s1].append(i)
			if s1 == k:
				ans.append([[0, i]])
			if s1 - k in c1:
				ans.append([[j + 1, i] for j in c1[s1 - k]])
		ans = sum(ans, [])
		return len(ans)


class Solution:

	def findSubArraySum(self, Arr, N, k):
		csum = 0
		pfsum = {}
		count = 0
		for i in Arr:
			csum += i
			if csum == k:
				count += 1
			if csum - k in pfsum:
				count += pfsum[csum - k]
			pfsum[csum] = pfsum.get(csum, 0) + 1
		return count


class Solution:

	def findSubArraySum(self, A, N, K):
		mp = dict()
		current_sum = 0
		count = 0
		for i in range(N):
			current_sum += A[i]
			if current_sum == K:
				count += 1
			if current_sum - K in mp:
				count += mp[current_sum - K]
			mp[current_sum] = mp[current_sum] + 1 if current_sum in mp else 1
		return count


class Solution:

	def findSubArraySum(self, Arr, N, k):
		d = {0: 1}
		su = 0
		cou = 0
		for i in Arr:
			su += i
			removesubarraysize = su - k
			if removesubarraysize in d:
				cou += d[removesubarraysize]
			elif su == k:
				cou += 1
			if su in d:
				d[su] += 1
			else:
				d[su] = 1
		return cou


class Solution:

	def findSubArraySum(self, arr, n, k):
		d = {0: 1}
		t = 0
		p = 0
		for i in range(0, n):
			p = p + arr[i]
			if d.get(p - k, 0) != 0:
				t = t + d.get(p - k, 0)
				d[p] = d.get(p, 0) + 1
			else:
				d[p] = d.get(p, 0) + 1
		return t


class Solution:

	def findSubArraySum(self, Arr, N, k):
		l = [0]
		s = 0
		for i in Arr:
			s = s + i
			l.append(s)
		g1 = dict()
		for i in range(len(l)):
			if g1.get(l[i]) != None:
				g1[l[i]].append(i)
			if g1.get(l[i]) == None:
				g1[l[i]] = [i]
		count = 0
		for i in range(len(l)):
			if g1.get(l[i] + k) != None:
				for j in range(len(g1[l[i] + k])):
					if g1[l[i] + k][j] > i:
						count = count + (len(g1[l[i] + k]) - j)
						break
		return count


class Solution:

	def findSubArraySum(self, Arr, N, k):
		d = {}
		c = 0
		summ = 0
		for i in Arr:
			summ = summ + i
			if summ == k:
				c = c + 1
			if summ - k in d:
				c = c + d[summ - k]
			if summ not in d:
				d[summ] = 1
			else:
				d[summ] += 1
		return c


class Solution:

	def findSubArraySum(self, Arr, N, k):
		count = 0
		m = {}
		sum = 0
		for i in range(N):
			sum += Arr[i]
			if sum == k:
				count += 1
			if sum - k in m:
				count += m[sum - k]
			if sum in m:
				m[sum] += 1
			else:
				m[sum] = 1
		return count


from collections import defaultdict

class Solution:

	def findSubArraySum(self, arr, N, k):
		c = 0
		d = defaultdict(int)
		cur_sum = 0
		for i in arr:
			cur_sum += i
			if cur_sum == k:
				c += 1
			z = cur_sum - k
			if z in d:
				c += d[z]
			d[cur_sum] += 1
		return c


class Solution:

	def findSubArraySum(self, Arr, N, k):
		d = {0: 1}
		cursum = 0
		c = 0
		for i in range(0, len(Arr)):
			cursum += Arr[i]
			if cursum - k in d:
				c += d[cursum - k]
			if cursum not in d:
				d[cursum] = 1
			elif cursum in d:
				d[cursum] += 1
		return c


class Solution:

	def findSubArraySum(self, arr, n, k):
		count = 0
		sm = 0
		mapper = dict()
		for i in arr:
			sm += i
			if sm == k:
				count += 1
			if mapper.get(sm - k):
				count += mapper.get(sm - k)
			mapper[sm] = 1 + mapper.get(sm, 0)
		return count


class Solution:

	def findSubArraySum(self, Arr, N, k):
		counter = {0: 1}
		ans = 0
		s = 0
		for a in Arr:
			s += a
			if s - k in counter:
				ans += counter[s - k]
			counter[s] = 1 + counter.get(s, 0)
		return ans


class Solution:

	def findSubArraySum(self, Arr, N, k):
		res = 0
		dic = {0: 1}
		cursum = 0
		for i in range(0, len(Arr)):
			cursum += Arr[i]
			val = cursum - k
			if val in dic:
				res += dic[val]
			dic[cursum] = dic.get(cursum, 0) + 1
		return res


class Solution:

	def findSubArraySum(self, Arr, N, k):
		sumArr = []
		prev = 0
		for num in Arr:
			sumArr.append(prev + num)
			prev += num
		sumsFound = {0: 1}
		ans = 0
		for _sum in sumArr:
			sumsFound[_sum] = sumsFound.get(_sum, 0) + 1
			if _sum - k in sumsFound:
				ans += sumsFound[_sum - k]
		return ans
[10, 12, 10, -10, 0]


class Solution:

	def findSubArraySum(self, Arr, N, k):
		ans = 0
		pre = 0
		d = {0: 1}
		for i in Arr:
			pre += i
			if pre - k in d:
				ans += d[pre - k]
			if pre not in d:
				d[pre] = 1
			else:
				d[pre] = d[pre] + 1
		return ans


from collections import defaultdict

class Solution:

	def findSubArraySum(self, arr, n, target):
		dct = defaultdict(lambda : 0)
		summ = 0
		count = 0
		for i in range(0, n):
			summ += arr[i]
			if summ == target:
				count += 1
			if summ - target in dct:
				count += dct[summ - target]
			dct[summ] += 1
		return count