题解 | #目标和#

题意整理

• 给定一个整数数组nums和一个整数target。
• 返回该数组能构成多少种不同的表达式等于target。

方法一（动态规划）

1.解题思路

本题可以转化为一个0-1背包问题。 我们将前面添加号的分为一组，记其累加和为a，将前面添减号的分为一组，记其累加和为b。如果能构成一个表达式，使得结果为target，则有$a+b=sum,a-b=targeta+b=sum,a-b=target$，其中sum为数组中所有数字的累加和。继续化简一下，可以得到：$a=(sum+target)\mathrm{/}2a=(sum+target)/2$。如果数组中存在若干数字之和等于a，则对应其中一个合法的表达式等于target。要想a存在，$sum+targetsum+target$必为偶数。

• 状态定义：$dp[i][j]dp[i][j]$表示i个元素时，有多少种不同的组合，其累加和为j。
• 状态初始化：初始化组成0的情况数为1。
• 状态转移：遍历nums数组中每一个数字，默认不选当前数字，即$dp[i+1][j]=dp[i][j]dp[i+1][j]=dp[i][j]$。如果j大于当前数字，则需要加上$j-nums[i]j-nums[i]$时的组合数，即$dp[i+1][j]+=dp[i][j-nums[i]]dp[i+1][j]+=dp[i][j-nums[i]]$。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int findTargetSumWays (int[] nums, int target) {
        //边界情况判断
        int n=nums.length;
        if(n==0) return 0;
        //记录累加和
        int sum=0;
        //遍历nums数组
        for(int num:nums){
            sum+=num;
        }
        //计算背包容量
        int V=(sum+target)/2;
        //如果为奇数，说明nums数组中找不打和为(sum+target)/2的若干数字
        if((sum+target)%2==1) return 0;
        
        //dp[i][j]表示i个元素时，有多少种不同的组合，其累加和为j
        int[][] dp=new int[n+1][V+1];
        //初始化
        dp[0][0]=1;
        for(int i=0;i<n;i++){
            for(int j=0;j<=V;j++){
                //默认不选当前数字
                dp[i+1][j]=dp[i][j];
                //如果选择当前数字，则需要加上j-nums[i]时的组合数
                if(j>=nums[i]){
                    dp[i+1][j]+=dp[i][j-nums[i]];
                }
            }
        }
        return dp[n][V];
    }
}

3.复杂度分析

• 时间复杂度：总共两次循环，需要执行$n\ast (V+1)n*(V+1)$次，所以时间复杂度是$O(n\ast V)O(n*V)$。
• 空间复杂度：需要额外大小为$(n+1)\ast (V+1)(n+1)*(V+1)$的dp数组，所以空间复杂度为$O(n\ast V)O(n*V)$。

方法二（空间优化）

1.解题思路

由于方法一中，每次状态转移，只与上一行的状态有关，所以可以只使用一个维度构建dp数组。每个数字只能选一次，所以需要倒序遍历背包容量，避免重复计算。

图解展示：

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int findTargetSumWays (int[] nums, int target) {
        //边界情况判断
        int n=nums.length;
        if(n==0) return 0;
        //记录累加和
        int sum=0;
        //遍历nums数组
        for(int num:nums){
            sum+=num;
        }
        //计算背包容量
        int V=(sum+target)/2;
        //如果为奇数，说明nums数组中找不打和为(sum+target)/2的若干数字
        if((sum+target)%2==1) return 0;
        
        //dp[j]表示有多少种不同的组合，其累加和为j
        int[] dp=new int[V+1];
        //初始化
        dp[0]=1;
        for(int i=0;i<nums.length;i++){
            //每个数字只选一次，所以需要倒序遍历，避免重复
            for(int j=V;j>=nums[i];j--){
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[V];
    }
}

3.复杂度分析

• 时间复杂度：总共两次循环，需要执行$n\ast (V+1)n*(V+1)$次，所以时间复杂度是$O(n\ast V)O(n*V)$。
• 空间复杂度：需要额外大小为$V+1V+1$的dp数组，所以空间复杂度为$O(V)O(V)$。