494. 目标和 - 力扣（LeetCode）

一、题目

给你一个整数数组 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

二、代码

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        int[] arr = new int[n];
        // 将nums迁移到另一个数组中，对另一个数组操作
        // nums数组都是非负数，求他们的累加和，得到最大可能的累加数量
        for (int i = 0; i < n; i++) {
            arr[i] = nums[i];
            sum += arr[i];
        }

        // 两个优化点：
        // 1、计算所有数的累加和假设是sum，如果target>sum，不可能有答案
        // 2、如果所有数加起来是个奇数，同样一批数要么奇数，要么偶数，如果target跟sum奇偶性不一样（(target & 1) ^ (sum & 1)) != 0）, 那么一定0种方法
        if (Math.abs(target) > sum || ((target & 1) ^ (sum & 1)) != 0) {
            return 0;
        }

        // dp缓存，因为存在负数情况，所以这里用HashMap
        HashMap<Integer, HashMap<Integer, Integer>> dp = new HashMap<>();

        // 来对dp赋初值。当index=n时赋值，只有当rest==0时是1，其他情况都是0
        HashMap<Integer, Integer> tempMap = new HashMap<>();
        for (int i = -sum; i <= sum; i++) {
            // 只有rest为0时，才赋值为1
            if (i != 0) {
                tempMap.put(i, 0);
            } else {
                tempMap.put(i, 1);
            }
        }
        // 完成赋初值
        dp.put(n, tempMap);

        // 每一层都依赖他们的下面一层的数据（递归函数都是index+1），所以我们确定是自底向上赋值
        for (int index = n - 1; index >= 0; index--) {
            HashMap<Integer, Integer> tMap = new HashMap<>();
            // 至于从左往右还是从右往左，不重要，反正每一层的数都是依赖下面一层，下面一层所有的数一定都已经计算出来了
            for (int rest = -sum; rest <= sum; rest++) {
                int ans = 0;
                // 这里要注意判断rest + arr[index]不要超过-sum~sum的范围，因为在赋初值的时候只赋值到了-sum~sum位置的值，如果这里不判断，就有可能取到越界位置的值，越界位置的是在本题的含义中是无意义的
                if (rest + arr[index] <= sum && rest + arr[index] >= -sum) {
                    ans = dp.get(index + 1).get(rest + arr[index]) ;
                }
                // 这里也要判断rest - arr[index]不要超过-sum~sum的范围
                if (rest - arr[index] <= sum  && rest - arr[index] >= -sum) {
                    ans += dp.get(index + 1).get(rest - arr[index]);
                }
                // 将计算的rest-ans的键值对添加到Map中
                tMap.put(rest, ans);
            }
            // 将当前index和rest情况下的答案ans添加到do中
            dp.put(index, tMap);
        }
    
        return dp.get(0).get(target);
    }
}

三、解题思路 

比较简单的一道动态规划题目。其中注意有两个可以优化的点：

1. 计算所有数的累加和假设是sum，如果target>sum，不可能有答案。
2. 如果所有数加起来是个奇数，同样一批数要么奇数，要么偶数，如果target跟sum奇偶性不一样, 那么一定0种方法。