图和树的bfs和dfs的区别是：
DFS and BFS of map is process of spanning tree, there is not a root
But for tree, usual not give us a adjacent matrix or adjacent list. The order of DFS is fixed
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
# s[i] = nums[0] + sum[1] + ---- + nums[i - 1] = s[i - 1] + nums[i - 1]
# nums[j] = s[j + 1] - s[j] j >= 0 s[0] = 0
s = [0] * (len(nums) + 1)
for i, num in enumerate(nums):
s[i + 1] = s[i] + nums[i]
# subarray sum equals k => s[j] - s[i] = k => s[i] = s[j] - k
# cnt have a time dimension. when we have s[j], we should only check s[i] where i<j, and record s[i] = s[j] - k. It is equal to scan number i between 0 to j - 1, but we can find that where i pass, j must pass before.This is a problem how many times you appear, which is Problem for Hash table. So we can record the frequency each number between s[0] to s[j - 1], when j pass, we don't need to i to pass through any more.
# the most artful thing is: we need j only to search before to avoid duplicate, and that happens to fit the requirement of using Hash table optimizing.
# another artful thing is : we transform sum of a array to relationship of this array's sum array, which is widely used in high school array problems
ans = 0
cnt = defaultdict(int)
for j, sum in enumerate(s):
ans += cnt[sum - k]
cnt[sum] += 1
return ans