Saved from https://leetcode.com/problems/subarray-sum-equals-k/

lc560

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        """ 
        Idea: find (i, j) where prefix_sums_j - prefix_sums_i == k
        tip: sum(i,j)=sum(0,j)-sum(0,i), 
        where sum(i,j) represents the sum of all the elements from index i to j-1.
        """
        sum_counts = defaultdict(int)
        sum_counts[0] = 1
        accumulate_sum = 0
        count = 0
        for num in nums:
            accumulate_sum += num
            if accumulate_sum - k in sum_counts:
                count += sum_counts[accumulate_sum - k]
            sum_counts[accumulate_sum] += 1
            # sj - si = k -> check sj exist by look up (si + k)
            # if k == 0, there always exist sum_counts[sum_i + k]                
        return count

    def naive_solution(self, nums: List[int], k: int) -> int:
        """Time limit exceeded"""
        count = 0
        n = len(nums)
        for start in range(n):
            for end in range(start+1, n+1):
                if sum(nums[start:end]) == k:
                    count += 1
        return count