'''
不懂的可以参考: https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/hot-100-he-wei-kde-zi-shu-zu-python3-cong-bao-li-j/
[1:29] Start

Thought Process
1. [Brute Force]

for i -> n
 for j -> (i, n)
 find sum of nums[i:j + 1] == target

Time: O(N^3)


2. PreSum

for i -> n
 preSum = [0] * len(arr)
 for j -> (i, n):
 if preSum[j] - preSum[i] == k
 add to res

Time: O(N^2)


3. preSum

because: preSum[j] - preSum[i] == k

so: preSum[i] == preSum[j] - k

because we always iterate i before j
we store preSum[i] in hash
and while we iterate J, we do preSum[j] - k, and see if it's in hash.

Time: O(N)

'''

# preSum + O(N^2)
class Solution(object):
 def subarraySum(self, nums, target):
 if not nums: return 0
 n = len(nums)
 res = 0
 for i in range(n):
 preSum = 0
 for j in range(i, n):
 preSum += nums[j]
 if preSum == target:
 res += 1
 return res

# preSum + hash O(N)
class Solution(object):
 def subarraySum(self, nums, target):
 if not nums: return 0
 dic = {0 : 1}
 preSum = 0
 res = 0
 for i in range(len(nums)):
 preSum += nums[i]
 if preSum - target in dic:
 res += dic[preSum - target]
 dic[preSum] = dic.get(preSum, 0) + 1 
 return res