[link](https://leetcode.com/problems/subarray-sum-equals-k/)

---

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

#### Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

#### Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

#### Constraints:

- 1 <= nums.length <= 2 * 104
- -1000 <= nums[i] <= 1000
- -107 <= k <= 107

---

The method initializes a dictionary prefixSum, which will store the cumulative sums of the elements encountered so far. The key represents the cumulative sum, and the value represents the count of occurrences of that sum. The variable curSum is initialized to 0. It will be used to keep track of the current cumulative sum of the subarray as we iterate through nums. The variable res is initialized to 0. It will be used to count the total number of contiguous subarrays whose sum equals k.

The method then iterates through the nums list using a loop. At each iteration, the curSum is updated by adding the current element n to it. The variable diff is calculated as the difference between the curSum and the target value k. If there is a contiguous subarray with the sum equal to k, then the sum of the subarray before the current element n would be equal to curSum - k. The variable diff will store this difference. The variable res is updated by adding the value of prefixSum[diff] to it. This value represents the count of contiguous subarrays with the sum equal to k.

The prefixSum[curSum] is updated to keep track of the count of the current cumulative sum. If the curSum is not already present in the prefixSum dictionary, it is initialized with a value of 1. If it is already present, its value is incremented by 1.

After completing the loop, the res variable will contain the total number of contiguous subarrays in nums whose sum equals k. Finally, the method returns the res.

#### Solution 1

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        prefixSum = {0: 1}
        curSum = 0
        res = 0
        for n in nums:
            curSum += n
            diff = curSum - k
            res += prefixSum.get(diff, 0)
            prefixSum[curSum] = 1 + prefixSum.get(curSum, 0)

        return res

O(T): O(n)
O(S): O(n)