[LeetCode] 560. Subarray Sum Equals K

560. Subarray Sum Equals K

Medium

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

---

문제 풀이

• 이어져 있는 부분 배열의 합이 K 랑 같은 것이 몇개 있는지 찾아야한다. 
• 문제 자체는 간단한데 제한사항을 보면 배열의 최대 길이가 2 * 10^4 이다. 
• 그렇다면 브루트 포스로는 거의 풀 수없다고 봐야한다. 1 자리부터 배열 전체 길이 까지 확인해야 봐야하기 때문에 O(n^3) 이 걸리기 때문이다. 
• Hash table 을 사용해서 풀도록 하자
• Two Sum 문제와 비슷한 접근 방식을 사용한다. 
• 해쉬 테이블에 저장할 데이터는 (합, 존재 갯수) 이며 첫 값 0, 1 를 넣는다.
• 배열의 첫 값부터 연속적으로 더해지는 값을 해쉬 테이블에 저장해 나간다. 
• 그 연속된 합에서 만일 k 를 뺀 값이 존재한다면 답을 새줘야 한다. 
• 그 이유는, 현재 위치까지 더한 모든 값에서 k 를 뺀 값은 이전까지 더해져온 값이라고 볼 수 있기 때문에 그 값이 해쉬 테이블에 존재한다면 그 값부터 현재 전체 값 - k 값 위치까지의 합이라고 볼 수 있다. 
• 쉽게 말해, 1, 2, 3 에서 k 가 3 이라고 해보자. 
• 3 값까지 올때, (0, 1), (1, 1), (3, 1) 이 해쉬 테이블에 저장이 되었고 현재 총 합의 값은 6 이다. 
• 1 부터 3 까지의 합이 6 이며, 6 에서 k 를 뺀 값 3 이 해쉬 테이블에 있는지 확인한다. 
• 다시말해 6 에서 k 를 빼면 3인데 해쉬 테이블에 (3, 1) 이 존재한다. 
• 첫 번째랑 두 번째 배열의 값을 연속적으로 더한게 3 이다. 
• 이때 답 갯수를 늘려주는데, 그 이유는 위에서 설명했듯이 index 가 1 인 위치까지의 합이 3 이며 현재 총합에서 3 을 빼면 3 이기 때문에 성립하게 된다. 
• 지금까지 출현한 모든 연속 배열의 합을 저장하는 이유는 한가지가 더 있다. 
• 문제 제한 사항을 보면 음수 값도 존재한다. 
• 지금까지 합쳐 졌던 연속된 배열의 합들이 중복이 될 가능성이 있기 때문이다. 

소스 코드

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        hash_table = defaultdict(int)
        hash_table[0] = 1
        total = 0
        n_len = len(nums)
        ans = 0
        for i in range(n_len):
            total += nums[i]
            if total - k in hash_table:
                ans += hash_table[total - k]
            
            hash_table[total] += 1
        return ans