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


  • 0
    W

    #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

  • 0
    J

    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
    

Log in to reply
 

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