0
\$\begingroup\$

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

For example:

Input: nums = [1,1,1], k = 2

Output: 2

The length of the array is in range [1, 20,000]. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

I came up with the following solution, which fails for a list with a 10,000 elements due to maximum recursion depth.

What changes can I make in the following code to improve it? Also, I am learning to use recursion, so what best practices can I employ for problems of this kind?

class Solution(object):
    def subarraySum(self, nums, k):  #driver method
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if k==0:
            return 0
        return self.func2(0,nums,k,[],0) 

    def func2(self,index,nums, k, path, cnt):
        """
        index= index of the array
        nums=input array
        k=sum
        path=elements seen so far in contiguous manner whose sum is less than or equal to k
        cnt=counter of no of subarrays found so far
        """
        if index==len(nums):
            return cnt
        if nums[index]+sum(path)<k: #if total sum is less than k
            path.append(nums[index])
            cnt=self.func2(index+1,nums,k,path, cnt)
        elif nums[index]+sum(path)==k: #if total sum is equal to k
            path.append(nums[index])
            path=path[1:]
            cnt+=1
            cnt=self.func2(index+1,nums,k,path,cnt)
        else: #if total sum > k
            path=path[1:]
            if len(path)>0:
                cnt=self.func2(index,nums,k,path,cnt)
            else:
                cnt=self.func2(index+1,nums,k,path,cnt)           
        return cnt
\$\endgroup\$
2
\$\begingroup\$

What you implemented is different from what you were asked. Both the numbers in the array as well as k can be positive and negative, while it seems like you assumed both are strictly positive.

Even if you made those assumptions, it still doesn't produce the desired output. For example, if your list of numbers were 5,10,2,4 and your sum is 12, then your subroutine would return 0 when it should return 1.

\$\endgroup\$
  • \$\begingroup\$ That's right, it does not work for some cases, how do I make the necessary changes? \$\endgroup\$ – Ashwin V Jan 20 '18 at 6:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.