我来给你讲解 LeetCode 第 494 题「目标和」。

题目描述

给你一个整数数组 nums 和一个整数 target。向数组中的每个整数前添加 '+' 或 '-'，然后串联起所有整数，可以构造一个表达式。返回可以通过上述方法构造的、运算结果等于 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

解题思路分析

第一步：问题转化

这个问题可以转化为一个数学问题：

• 设所有添加 '+' 的数字之和为 sum_positive
• 设所有添加 '-' 的数字之和为 sum_negative
• 那么：sum_positive - sum_negative = target
• 同时：sum_positive + sum_negative = sum(nums)（所有数字的和）

将两个等式相加得到：
2 × sum_positive = target + sum(nums)

所以：sum_positive = (target + sum(nums)) / 2

问题转化为：在 nums 中找到一个子集，使得子集的和等于 (target + sum(nums)) / 2。

第二步：边界条件检查

1. 如果 target + sum(nums) 是奇数，无解（因为需要除以2得到整数）
2. 如果 target 的绝对值大于 sum(nums)，无解
3. 如果 target + sum(nums) < 0，无解

第三步：动态规划解法

这是一个经典的0-1背包问题：从 nums 中选取若干个数，使得它们的和等于目标值。

定义 dp[j] 表示：填满容量为 j 的背包，有 dp[j] 种方法。

状态转移方程：
dp[j] = dp[j] + dp[j - nums[i]]

意思是：对于当前数字 nums[i]，如果不选它，方法数是 dp[j]；如果选它，方法数是 dp[j - nums[i]]。

详细解题步骤

步骤1：计算总和并检查边界条件

def findTargetSumWays(nums, target):
    total = sum(nums)
    
    # 边界条件检查
    if abs(target) > total:  # target绝对值太大
        return 0
    if (target + total) % 2 == 1:  # 和为奇数
        return 0
    if target + total < 0:  # 和为负数
        return 0
    
    # 计算目标子集和
    target_sum = (target + total) // 2

步骤2：初始化动态规划数组

    # dp[j] 表示和为j的方法数
    dp = [0] * (target_sum + 1)
    dp[0] = 1  # 和为0只有1种方法：什么都不选

步骤3：动态规划过程

    # 遍历每个数字
    for num in nums:
        # 从后往前遍历，避免重复计算
        for j in range(target_sum, num - 1, -1):
            dp[j] = dp[j] + dp[j - num]
    
    return dp[target_sum]

完整代码实现

def findTargetSumWays(nums, target):
    total = sum(nums)
    
    # 边界条件检查
    if abs(target) > total or (target + total) % 2 == 1 or target + total < 0:
        return 0
    
    target_sum = (target + total) // 2
    
    # 初始化DP数组
    dp = [0] * (target_sum + 1)
    dp[0] = 1
    
    # 动态规划
    for num in nums:
        for j in range(target_sum, num - 1, -1):
            dp[j] += dp[j - num]
    
    return dp[target_sum]

示例演示

以 nums = [1,1,1,1,1], target = 3 为例：

1. total = 5
2. target_sum = (3 + 5) // 2 = 4
3. 问题转化为：在5个1中选出若干个数，使得和为4
4. 从5个1中选4个1：有C(5,4) = 5种方法
5. 结果确实是5

复杂度分析

• 时间复杂度：O(n × target_sum)，其中n是数组长度
• 空间复杂度：O(target_sum)

关键点总结

1. 问题转化：将加减问题转化为子集和问题
2. 边界处理：注意各种无解情况的判断
3. 动态规划：使用0-1背包的思路求解
4. 遍历顺序：内层循环需要从后往前，避免重复计算

这个解法将原问题的指数复杂度优化到了多项式复杂度，是典型的动态规划应用。