leet code - 560. Subarray Sum Equals K(Medium, hashmap, prefix sum)

560. Subarray Sum Equals K

 

Solved

 

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

주어진 배열에서 **부분 배열(subarray)**의 합이 정확히 k가 되는 경우의 수를 구하는 문제.

 

input length 10 ^ 4 로 최악의 경우엔 브루탈 포스 O(n^3)의 시간 복잡도가 된다.

 

이중 포문으로 모든 서브어레이를 만들고, 해당 서브어레이에 대해 다시 sum을 수행한다면, 이는 O(n^3)의 시간 복잡도를 지닐것이다.

 

어떻게 최적화 할 수 있을까?

 

일단 prefix_sum 을 활용하게 되면, sum에 대한 시간 복잡도를 최적화 할 수 있다.

prefix_sum - complement = k

가 될 것이다. 즉 연속적으로 이어나가는 prefix_sum 에서 어떤 부분 배열의 합 complement 를 빼면 k 가 될 수있다.

 

아에 빼야하는 complement 서브어레이의 등장 횟수를 찾는 방식으로 간접적으로 답을 찾을 수 있다.

즉 complement = prefix_sum -k의 등장횟수를 찾는다.

 

그리고 그 등장횟수를 cnt 에 더하며 한번의 순회로 답을 찾는다.

 

 

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        prefix_sum = 0
        count = 0
        prefix_sum_map = defaultdict(int)
        prefix_sum_map[0] = 1  # 누적합 0이 처음에 1번 있다고 가정

        for num in nums:
            prefix_sum += num
            count += prefix_sum_map[prefix_sum - k]
            prefix_sum_map[prefix_sum] += 1

        return count