[LeetCode] 560 | Subarray Sum Equals K | Python

---

문제 링크: https://leetcode.com/problems/subarray-sum-equals-k/

---

문제

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

---

조건

• 1 <= nums.length <= 2 * $10^4$
• -1000 <= nums[i] <= 1000
• $-10^7$ <= k <= $10^7$

---

내 풀이

sum(nums[:7]) - sum(nums[:3]) = k를 만족한다면, sum(nums[3:7]) = k라는 것을 알 수 있다.

이를 이용해 문제를 푼다.

cur_sum에는 현재까지의 합을 저장해두고, sums 리스트에는 cur_sum에 나온 모든 수와 그 갯수를 저장해둔다.

그렇기때문에 cur_sum - k에 해당하는 수가 sums에 존재한다면, 그 갯수만큼 ans에 더한다.

---

코드

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