560.Subarray_Sum_Equals_K(Medium).md

560. Subarray Sum Equals K (Medium)

Date and Time: Nov 12, 2024, 12:06 (EST)

Link: https://leetcode.com/problems/subarray-sum-equals-k/

Question:

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 * 10^4

• -1000 <= nums[i] <= 1000

• -10^7 <= k <= 10^7

Walk-through:

We use hashmap{diff: counts} to save diff = curSum - k with its counts. If nums = [1, 1], k = 2, in this case, curSum = 2, diff = 2 - 2 = 0, so we know this is a valid subarray sum equals k, update res += hashmap.get(diff, 0) + 1 which will be {0: 1}.

For every curSum, we need to update its counts in hashmap, hashmap[curSum] = hashmap.get(curSum, 0) + 1.

Python Solution:

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # Build a hashmap{diff: counts}, diff = curSum - k
        # If diff in hashmap, update res += hashmap[diff]. If curSum = 2, k = 2, in this case, diff = curSum - k = 0, and by default, hashmap[diff] = hashmap[0] = 1
        # Update curSum with counts += 1 in hashmap

        # TC: O(n), n = len(nums), SC: O(n)
        res, curSum = 0, 0
        hashmap = {0: 1}
        for n in nums:
            curSum += n
            diff = curSum - k
            res += hashmap.get(diff, 0)     # If diff in hashmap, update res with counts
            hashmap[curSum] = hashmap.get(curSum, 0) + 1    # Update curSum with counts into hashmap
        return res

Time Complexity: $O(n)$
Space Complexity: $O(n)$