# 58/80 passed, DP Python solution, failed on long input list, easy to understand

• #import numpy

class Solution(object):
def subarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""

``````    if nums == None:
return

numLen = len(nums)
#print "numLen = ", numLen

result = 0

#Typical DP needs two dimentional table
#table = [[0 for x in range(numLen+1)] for y in range(numLen+1)]
#this particular question requires only 1 dimentional table
#table = [0 for x in range(numLen+1)]
#print "1 table[numLen][numLen] = ", table
for i in range(1, numLen+1):
table = [0] * (numLen+1-i)
for j in range(i, numLen+1):
#print "i = ", i, " j = ", j
table[j-i] = table[j-1-i] + nums[j-1]
#table[j] = table[j-1] + nums[j-1]
if (table[j-i] == k):
result += 1

#print "2 table[numLen] = ", table
#print "result = ", result

return result``````

• I think there is no need to fill the DP table in this order. A simple brute force code like this will work, no extra list is needed.

``````class Solution(object):
def subarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""

n, result = len(nums), 0
for i in range(n):
sum = 0
for j in range(i, n):
sum += nums[j]
if sum == k:
result += 1
return result
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.