560. Subarray Sum Equals K - python3

560. 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.

My Answer 1: Time Limit Exceeded (85 / 89 test cases passed.)

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # [1,1], [1,1]
        # [1,2], [3]
        
        ans = 0
        
        dp = [0]*(len(nums)+1)
        
        for i in range(len(nums)):
            dp[i+1] = dp[i] + nums[i]
        
        dp.pop(0)
        
        for i in range(len(dp)):
            if dp[i] == k:
                ans += 1
            ans += dp[:i].count(dp[i] - k)
        
        return ans

for 문이로 도배하면 가능할 거 같기도 한데 양심상 dp 써봤읍니다..

근데 타임리밋이라 에바네요

통과 안된 예시) 1 이 10000 개 있음..^^

Solution 1: Accepted (Runtime: 260 ms - 57.03% / Memory Usage: 16.6 MB - 96.46%)

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        ans = 0
        
        dic = {}
        dic[0] = 1
        
        tmp = 0
        for i in range(len(nums)):
            tmp += nums[i]
            if tmp - k in dic:
                ans += dic[tmp-k]
            if tmp in dic:
                dic[tmp] += 1
            else:
                dic[tmp] = 1
        
        return ans

dic 이용

if tmp - k in dic: => subarray 가 될 수 있는 거니까 개수 모두 더하기

현재까지 모두 더한 값인 tmp 값도 1 증가