题目难度: 中等
今天继续更新 Leetcode 的剑指 Offer（专项突击版）系列, 大家在公众号 算法精选 里回复
剑指offer2就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
给定一个正整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
- 输入：nums = [1,1,1,1,1], target = 3
- 输出：5
- 解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2：
- 输入：nums = [1], target = 1
- 输出：1
提示：
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 1000
- 0 <= sum(nums[i]) <= 1000
- -1000 <= target <= 1000
题目思考
- 如何优化算法复杂度?
解决方案
- 分析题目, 每个数字都必须使用, 且要么使用原数字, 要么使用其相反数
- 所以我们可以遍历所有数字, 维护当前添加符号后的数字总和, 当遍历完成后如果其总和恰好等于 target, 就说明找到了一个有效解
- 以上就是典型的回溯思想, 具体做法如下:
- 函数传入当前下标和总和, 返回有效解的个数
- 如果当前下标超出数组范围, 则停止回溯, 根据其总和是否等于 target, 决定返回 1 还是 0
- 否则累加两种情况: 当前数字添加 '+' (原数字) 或 '-' (相反数) , 并更新下标以及总和继续回溯
- 不过回溯的时间复杂度达到了
O(2^N), 是否可以进一步优化呢? - 观察题目规模, 不难发现总和最大是 1000(全使用原数字), 而最小是-1000(全使用相反数), 我们可以将原来的回溯函数加上记忆化(Python3 的 functools.cache, 其他语言可以使用一个二维 memo 数组), 这样最多只需要处理
20*2000次运算, 相比回溯 (2^20) 有明显的优化, 使用空间换了时间 - 下面的代码有详细的注释, 方便大家理解
复杂度
- 时间复杂度
O(N*C): C 是数组和的值域范围, 由于可以全用负号, 所以就是[-1000,1000], 共计 2000, N 是元素数目 - 空间复杂度
O(N*C): 记忆化搜索最多保存 N*C 个数字
代码
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
n = len(nums)
@functools.cache
def dp(i, sm):
if i == n:
# 递归出口, 遍历完所有数字了, 如果和恰好等于target就有效
return 1 if sm == target else 0
# 累加使用加号和使用减号的两种方案数
return dp(i + 1, sm + nums[i]) + dp(i + 1, sm - nums[i])
return dp(0, 0)
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号