python solution O(n^2)


  • 0
    class Solution(object):
        def findTargetSumWays(self, nums, S):
    
            if nums is None or len(nums) == 0:
                return 0
            
            hs1 = {}
            hs2 = {}
            
            for i in range(len(nums)):
                if i == 0:
                    if nums[0] == 0:
                        hs1[0] = 2
                    else:
                        hs1[-nums[0]] = 1
                        hs1[nums[0]] = 1
                else:
                    for key in hs1:
                        if key + nums[i] not in hs2:
                            hs2[key + nums[i]] = hs1[key]
                        else:
                            hs2[key + nums[i]] += hs1[key]
                        if key - nums[i] not in hs2:
                            hs2[key - nums[i]] = hs1[key]
                        else:
                            hs2[key - nums[i]] += hs1[key]
                    hs1 = hs2
                    hs2 = {}
            
            if S in hs1:
                return hs1[S]
            else:
                return 0
    

Log in to reply
 

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