LC560.md

Problem: Subarray Sum Equals K

Difficulty: Medium

Description:

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

Examples:

Input: nums = [1,1,1], k = 2
Output: 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

Solutions:

The naive appraoch is always to produce all of the subarrays and find the one that meets the objective. This approach has a time complexity of O(N^3) and space complexity of O(N) where N is the size of array.

def subarraySum(nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: int
    :Time Complexity: O(N^3)
    :Space Complexity: O(N)
    """
    ans = 0
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            sub = nums[i : j + 1]
            if sum(sub) == k:
                ans += 1

    return ans

For the optimal solution, we can use the defaultdict data structure. This approach has a time complexity of O(N) and space complexity of O(N+K) where N is the size of array.

def subarraySum(self, nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: int
    :Time Complexity: O(N)
    :Space Complexity: O(N+K)
    """
    from collections import defaultdict

    seen = defaultdict(int)
    current_sum = 0
    ans = 0

    for num in nums:
        current_sum += num
        ans += seen[current_sum - k]
        seen[current_sum] += 1

    ans += seen[k]

    return ans