华为 OD 训练营 · 题解精讲
LC494.目标和
LC494.目标和
题目描述
给你一个整数数组 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
题目解析
解题思路
本题将每个数字前添加 + 或 -，等价于将数组分为两个子集 A（加号）和 B（减号）。设数组总和为 sum，A 的和为 sumA，B 的和为 sumB，则有：
sumA + sumB = sumsumA - sumB = target
两式相加得 2 * sumA = sum + target，即 sumA = (sum + target) / 2。问题转化为：从数组中选出若干数字，使其和恰好等于 sumA，求方案数——这是一个经典的 01 背包问题。
关键步骤
1. 预处理：计算 total = sum(nums)，若 (total + target) 为奇数或 bagSize = (total + target) // 2 为负数，直接返回 0。 2. 定义 DP 数组：dp[i][j] 表示从前 i 个数字中选出若干，和为 j 的方案数。初始化 dp[i][0] = 1（不选任何数字即可得到和为 0）。 3. 状态转移（外层遍历物品 i，内层遍历容量 j）：
- 若
j < nums[i-1]，当前物品无法放入：dp[i][j] = dp[i-1][j] - 否则：
dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[i-1]]（不选 + 选）
4. 返回 dp[len(nums)][bagSize]。
转移示意图（以 nums = [1,2,3], bagSize = 3 为例）：
dp[i][j] j=0 1 2 3
i=0 (空集) 1 0 0 0
i=1 (数字1) 1 1 0 0 ← 容量1可由数字1填满
i=2 (数字2) 1 1 1 1 ← 容量3可由(1+2)填满
i=3 (数字3) 1 1 1 2 ← 容量3有两种：1+2 或 3复杂度分析
- 时间复杂度：O(n × bagSize)，其中 n 为数组长度，bagSize ≤ sum(nums) ≤ 1000。
- 空间复杂度：O(n × bagSize)，使用二维 DP 数组。
参考代码
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
# 每个数字都有两种状态：被进行“+”， 或者被进行“-”
# 因此可以将数组分成 A 和 B 两个部分
# A 部分的数字全部进行“+”操作
# B 部分的数字全部进行“-”操作
# 设数组的和为 sum ，A 部分的和为 sumA ，B 部分的和为 sumB
# sumA + sumB = sum (1)
# 同时有： sumA - sumB = target (2)
# 将(1)式与(2)式相加，可以得到： 2sumA = sum + target (3)
# 即 sumA = (sum + target) / 2
# 所以，原问题转换为：
# 有一些物品，第 i 个物品的重量为 nums[i] ， 背包的容量为 sumA ，问：有多少种方式将背包【恰好填满】
# 先去计算总和
total = sum(nums)
# 再去计算背包容量
bagSize = (target + total) // 2
# 题目有可能出现 target 是一个很小的负数
# 比如 nums = [ 100 ] ，target = -200
# 这个时候 bagSize 就是负数了，直接输出0
if bagSize < 0 :
return 0
# 如果发现 target + sum 为奇数，则无解
# 比如 nums = [ 1 ] ，target = 2
# target + sum = 2 + 1 = 3 ，此时无解
# 因为 bagSize 必然是整数，即 (target + sum) / 2 必然是整数
# 那么只有 target + sum 为偶数才能得到整数
if (target + total) % 2 == 1 : return 0
# 在前 i 个数字中，凑出和为 j 的组合有多少种方法
# dp[0][0] 表示在前 0 个数字中，凑出和为 0 的组合，有多少种方法
dp = [[0] * (bagSize + 1) for _ in range(len(nums) + 1)]
# 初始化
for i in range(len(nums) + 1) :
# 在前 i 个数字中，凑出和为 0 的组合有多少种方法
# 答案是 1 种方法
# 即每次不选择第 i 个元素就行
dp[i][0] = 1
# 01 背包问题开始填充二维数组
for i in range( 1 , len(nums) + 1 ) :
for j in range(bagSize + 1) :
# 注意到 i 是从下标 1 开始访问的
# 1、背包容量小于当前元素
# 背包无法放入 nums[i - 1]
if j < nums[i - 1] :
dp[i][j] = dp[i - 1][j]
# 2、背包容量大于等于当前元素
# 背包可以放入 nums[i - 1]
else:
# 不选：方案数为 dp[i - 1][j]
# 选：方案数为 dp[i - 1][j - nums[i - 1]]
# 两者之和
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]]
# 返回结果
return dp[len(nums)][bagSize]