题解 | #目标和#

目标和

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

规则如下：

1.将数组里每个整数前面可以添加"+"或者"-"符号，组成一个表达式，例如[1,2]，可以变成”+1+2","+1-2","-1+2","-1-2"，这四种

2.只能添加"+"与"-"符号，不能添加其他的符号

3.如果构不成等于target的表达式，请返回0

4.保证返回的结果个数在整数范围内

方法一：回溯

具体方法

数组$numsnums$ 的每个元素都可以添加符号 + 或 -，因此每个元素有 2种添加符号的方法，$nn$个数共有 $2^{n}2^n$种添加符号的方法，对应 $2^{n}2^n$种不同的表达式。当$nn$个元素都添加符号之后，即得到一种表达式，如果表达式的结果等于目标数 $targettarget$，则该表达式即为符合要求的表达式。

可以使用回溯的方法遍历所有的表达式，回溯过程中维护一个计数器 count，当遇到一种表达式的结果等于目标数 target 时，将 count 的值加 1。遍历完所有的表达式之后，即可得到结果等于目标数target 的表达式的数目。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    static int count = 0;
    public int findTargetSumWays (int[] nums, int target) {
        // write code here
        //特殊情况 
        if(nums.length == 0)
            return 0;
        // dfs回溯
        dfs(nums,target,0,0);
        return count;
    }
    public void dfs(int[] nums, int target, int index, int sum){
        // 走到最后一个索引位置
        if(index == nums.length){
            // sum和等于target 就加一
            if(sum == target)
                count++;
        }
        else{
            // dfs回溯 +操作
            dfs(nums,target,index+1,sum + nums[index]);
            // dfs回溯 -操作
            dfs(nums,target,index+1,sum -nums[index]);
        }
    }
}

复杂度分析

时间复杂度：$O(2^n)O(2^n)$，其中$nn$是数组nums 的长度。回溯需要遍历所有不同的表达式，共有 2^n 种不同的表达式，每种表达式计算结果需要$O(1)O(1)$的时间，因此总时间复杂度是 $O(2^n)O(2^n)$。

空间复杂度：$O(n)O(n)$，其中 $nn$是数组 $numsnums$ 的长度。空间复杂度主要取决于递归调用的栈空间，栈的深度不超过 n。

。

方法二：动态规划

具体方法

数组的和为sum，假设取-号的元素和为$newtargetnewtarget$，则其余的元素和为$sum-newtargetsum-newtarget$，则可以得到如下公式

$sum-newtarget-newtarget=targetsum-newtarget\; -newtarget\; =\; target$

$newtarget=\mathrm{（}sum-target\mathrm{）}\mathrm{/}2newtarget\; =\; （sum-target）/2$

由于数组 nums 中的元素都是非负整数，neetarget 也必须是非负整数，所以上式成立的前提是sum−target 是非负偶数。若不符合该条件可直接返回 0。

定义二维数组$dp[i][j]dp[i]\; [j]$ 表示取数组的前i元素中的若干个得到和为j的方案数，本题要求的就是$dp[n][newtarget]dp[n]\; [newtarget]$

则$dp[0][0]=1dp[0]\; [0]\; =\; 1$

状态转移方程为

• $j>nums[i],dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]]j>nums[i]\; ,dp[i]\; [j]\; =\; dp[i-1]\; [j]\; +\; dp[i-1]\; [j-\; nums[i]]$

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int findTargetSumWays (int[] nums, int target) {
        // write code here
        if(nums.length== 0){
            return 0;
        }
        // 求解数组的和
        int sum = 0;
        for(int num:nums){
            sum += num;
        }
        // 判断sum- target是否是偶数
        int temp = sum - target;
        // 说明不存在满足和为target的方案数
        if(temp < 0 || temp %2 !=0)
            return 0;
        int newtarget = temp/2;
        int [][]dp = new int[nums.length+1][newtarget+1];
        //初始化dp数组
        dp[0][0] = 1;
        for(int i=1;i<=nums.length;i++){
            int num = nums[i-1];
            for(int j=0;j<=newtarget;j++){
                if(j<num)
                    dp[i][j] = dp[i-1][j];
                else{
                    dp[i][j] = dp[i-1][j]+dp[i-1][j-num];
                }
            }
        }
        return dp[nums.length][newtarget];
    }
}

复杂度分析

• 时间复杂度：$O\mathrm{（}n\ast newtarget\mathrm{）}O（n\; *\; newtarget）$，两层循环
• 空间复杂度：$O\mathrm{（}n\ast newtarget\mathrm{）}O（n\; *\; newtarget）$，一个二维的dp数组

由于dp 的每一行的计算只和上一行有关，因此可以使用滚动数组的方式，去掉dp的第一个维度，将空间复杂度优化到还可以优化空间复杂度：优化到$O\mathrm{（}newtarget\mathrm{）}O（newtarget）$

优化后代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int findTargetSumWays (int[] nums, int target) {
        // write code here
        if(nums.length == 0)
            return 0;
        int sum = 0;
        //求和
        for (int num : nums) {
            sum += num;
        }
        // 判断是否可以和为target的组合
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }
        int newtarget = diff / 2;
        int[] dp = new int[newtarget + 1];
        dp[0] = 1;
        // for循环遍历每个元素
        for (int num : nums) {
            for (int j = newtarget; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[newtarget];
    }
}