目标和leetcode

Question

我正在设法解决这个问题。

给你一个非负整数的列表，a1，a2，.，an和一个目标，S，现在你有两个符号+和-。对于每个整数，您应该从+和-中选择一个作为它的新符号。找出有多少种方法分配符号使整数之和等于目标S。

我的解决办法是：

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        ways = 0 
        def dfs(index, s):
            nonlocal ways 
            if index == len(nums):
                if s == 0:
                    ways +=1 
            else:
                dfs(index+1, s-nums[index])
                dfs(index+1, s+nums[index])

        dfs(0, S)
        return ways

如何从时间复杂度的角度对此进行优化？

请不要评论该方法可以单独作为一个函数存在；这是leetcode使用的模板，不能更改。

https://leetcode.com/problems/target-sum/

Answer 1

您的解决方案计算通过将符号+1和-1分发给数字而获得的所有可能的目标和。对于具有n数字(即2^n组合)的数组。

这是一个典型的情况，其中动态规划是有利的。不是搜索导致目标和S的所有组合，而是计算导致范围内任何目标和的组合数。

这里的关键提示是

1. 给定数组中的元素之和不会超过1000。

这意味着只有-1000和1000之间的目标和可以通过将符号+1和-1分配给数字，即“只”2001可能的目标和来获得。

因此，我们的想法是维护一个长度为L的列表( list 2001 )，它对应于可能的目标和-1000 \ldots 1000。在下面的迭代中的每一点上，L[i + 1000]都是获得目标和i的方法的数量，其中包含到目前为止遇到的数字。

最初，L[1000] = 0和所有其他条目为零，因为0是唯一可以使用任何数字获得的目标和。

然后遍历给定的数字数组并更新列表L。

最终，L[S + 1000]是使用所有给定数字获得目标和S的所需方法的数目。

这种方法具有O(n) 时间复杂度，这比原始方法的O(2^n)要好得多。

Answer 2

Python有递归限制。默认情况下，这大约只有1000个堆栈级别深，取决于您的输入，这个上限可能通过递归达到。

如果您使用了与作业相同的输入，那么我很难相信您超时了。您的函数将只被调用1+2^4 = 17次。

我用作业输入运行它，它马上就完成了。