560. Subarray Sum Equals K

MediumLeetCode

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

How to solve the problem

• Brute Force

class Solution:
    def subarraySum(self, nums:List[int], k:int) -> int:
        counter = 0
        for start in range(len(nums)):
            for end in range(start, len(nums)):
                s = 0
                for i in range(start, end + 1):
                    s += nums[i]
                if s == k:
                    counter += 1
        return counter

• Hashing

The key is to leverage previously computed prefix sums stored in a hashmap, so each new subarray sum can be obtained by subtraction instead of recomputation.

class Solution:
    def subarraySum(self, nums:List[int], k:int) -> int:
        pre = 0
        counter = 0
        hashmap = defaultdict(int)
        hashmap[0] = 1
        for num in nums:
            pre += num
            if pre - k in hashmap:
                counter += hashmap[pre-k]
            hashmap[pre] += 1
        return counter

Complexity

• Brute Force: Time complexity: O(n^3), Space complexity: O(1)
• Hashing: Time complexity: O(n), Space complexity: O(n)
  • Each element is visited once, and hash map operations are O(1) on average