Skip to Content

Subarray sum equals K - Prefix Sum problem

Home | Coding Interviews | Arrays and Strings | Subarray sum equals K - Prefix Sum problem

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.

class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        count = 0
        sums = 0
        d = dict()
        d[0] = 1
        
        for i in range(len(nums)):
            sums += nums[i]
            count += d.get(sums-k,0)
            d[sums] = d.get(sums,0) + 1
        
        return(count)

Posted by Jamie Meyer 7 months ago

Related Problems

Given a string S and an integer K, return the length of the longest substring of S that contains at most K distinct characters.

Given an integer array nums, you need to find one continuous subarray such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing order.

Return the shortest such subarray and output its length.

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Given an integer array nums sorted in increasing order, remove the duplicates in place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.