题解 | #目标和#

题目分析

1. 题目给出的输入有一个数组，和一个目标值target
2. 题目的要求是，用户可以任意指定数组中数字的正负，只要求经过添加符号后的数字可以累计为目标值target即为一种方案
3. 题目要求我们最终返回一共有几种方案。

方法一：递归

• 实现思路

  • 我们可以以递归的思路来帮我们实现暴力尝试的过程

  • 我们自定义一个递归函数findTarget函数，表示的含义是在nums数组中，目标最后累计达到target值，当前递归函数正在处理的数字是nums[left]，当前累计的结果储存在res中

  • 在递归函数中，我们设置返回条件当处理的数字下标到达数组末尾，数字全部经过正负号处理完毕后，如果有res == target，我们计方案数+1，否则当前设置正负符号不是一种合法方案，计数为0

  • 如果当前还没有处理完所有数字，则递归地在res中累计与当前数字地正数结果和负数结果分别加和，并继续数组中下一个数字位置地递归处理。

  • 最终返回findTarget的结果就是所有的方案数量。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int findTarget(vector<int>& nums, int target, int left, int res) {
        if(nums.size() == left) {			// 递归函数退出条件
            if(res == target) return 1;		// 如果加和为target计数方案+1
            else return 0;					// 否则计数方案+0
        } else {
            return findTarget(nums, target, left+1, res+nums[left]) + findTarget(nums, target, left+1, res-nums[left]);	// 左右两支进行计算
        }
    }
    
    int findTargetSumWays(vector<int>& nums, int target) {
        // write code here
        if(nums.size()==0) return 0;
        return findTarget(nums, target, 0, 0);
    }
};

复杂度分析

• 时间复杂度：$O(2^n)O(2^n)$，其中n是数组长度，由于暴力遍历了所有情况，每个数字都有正负两种取法，因此时间复杂度为指数级别。
• 空间复杂度：$O(n)O(n)$，递归栈的最大深度就是数组长度，因此空间代价是线性的

方法二：动态规划（0-1背包问题）

• 实现思路
  • 通过一定的数学推导我们知道，题目可以转化为0-1背包问题
    • 假设所有标记为正数的数据和为$pospos$，标记为负数的数据和绝对值为$negneg$，因此我们有$pos+neg=sumpos+neg=sum$，其中$sumsum$是给定数组的所有数字之和，还有$pos-neg=targetpos-neg=target$，因此可以推导得出$neg=\frac{sum-target}{2}neg=\backslash frac\{sum-target\}\{2\}$。
    • 因此如果$sum-targetsum-target$非偶数，则方案数一定为0，首先要保证两者之差为偶数这一点才能继续我们的计算。
  • 因此当前问题转化为从n个数字中，挑选出和为neg的方案数的0-1背包问题(好比n个可选的物品有各自的重量，求挑选出足够的物品要完全装满能够称重为neg的背包的方案数)
  • 我们定义dp[i][j]的含义是在前i个物品中，挑选出能够达到j数量的方案数，因此最终应该返回的结果是dp[n][neg]
  • 特殊边界限制是dp[0][0] = 1，对于0个物品达到0的目标，显然只有一种方案
  • 对于其他情况（0<i<=n,0<=j<=neg）有
  • 最终返回dp[n][neg]即可

#include <numeric>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int findTargetSumWays(vector<int>& nums, int target) {
        // write code here
        if(nums.size() == 0) return 0;						// 特殊条件处理
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if((sum-target) & 1 == 1) return 0;
        int neg = (sum-target)/2;							//neg 表示为 (sum-target)/2
        int n = nums.size();
        
        // dp[i][j] 表示前i个数据中装满j的方案数，最终返回dp[n][neg]
        vector<vector<int>> dp(n+1, vector<int>(neg+1, 0));
        dp[0][0] = 1;
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= neg; j++) {
                if(j < nums[i-1]) dp[i][j] = dp[i-1][j];				// 动态规划递推式1
                else dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];	 // 动态规划递推式2
            }
        }
        
        return dp[n][neg];
    }
};

复杂度分析

• 时间复杂度：$O(n\times neg)O(n\times neg)$，其中$nn$是nums数组的长度，$negneg$是数组元素之和减去目标值，动态规划中所有的状态都需要计算出来，因此时间代价也就是计算dp数组的时间代价
• 空间复杂度：$O(n\times neg)O(n\times neg)$，其中$nn$是nums数组的长度，$negneg$是数组元素之和减去目标值，维护dp动态规划数组的空间开销大小