LeetCode [560]: Subarray Sum Equals K

📌 LeetCode [560]: Subarray Sum Equals K

🔗 문제 링크

---

문제 설명 📄

정수 배열 nums와 정수 k가 주어졌습니다.
배열 nums에서 합이 정확히 k인 연속적인 부분 배열의 개수를 반환하세요.

---

문제 해결 접근 🚀

1. 누적합(Prefix Sum)과 해시맵 활용
   • 누적합을 계산하며 이전에 나타난 누적합의 빈도를 해시맵(pattern)에 저장합니다.
   • 현재 누적합에서 k를 뺀 값이 해시맵에 존재한다면, 해당 값이 등장했던 지점 이후의 부분 배열이 k와 같은 합을 가진다는 뜻입니다.
2. 효율적인 계산
   • 한 번의 순회로 모든 경우를 계산하며, 시간 복잡도는 O(n)입니다.
   • 공간 복잡도는 누적합의 종류에 비례하며, 최악의 경우 O(n)입니다.

---

Solution 💻

from collections import defaultdict

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        pattern = defaultdict(int)
        pattern[0] = 1  # 초기값: 합이 0인 부분 배열
        
        answer = 0
        cSum = 0  # 현재 누적합
        
        for num in nums:
            cSum += num  # 누적합 갱신
            
            # cSum - k가 존재하면, 해당 지점 이후 부분 배열 합이 k
            if cSum - k in pattern:
                answer += pattern[cSum - k]
            
            # 현재 누적합을 해시맵에 저장
            pattern[cSum] += 1
        
        return answer

---

시간 복잡도 분석 ⏲️

• 누적합 순회: O(n) (배열 크기만큼 순회)
• 총 시간 복잡도: O(n)

---

공간 복잡도 분석 🗄️

• 해시맵 저장 공간: 최대 O(n) (각기 다른 누적합의 수)
• 총 공간 복잡도: O(n)