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
