题目描述

题目链接：494. 目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

  • 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例1：

1
2
3
4
5
6
7
8
输入：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：

1
2
输入：nums = [1], target = 1
输出：1

提示：

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000

我的题解

方法一：动态规划

思路

由题意，求出数组的和为sum，那么添加运算符号后，则最终的结果范围为：-sum~sum，

设dp[i][j]为前i个数中和为j的个数，因此每一个状态都有dp[i-1][0~j]推出，以实例一为例：

1
2
3
4
  -5 -4 -3 -2 -1 0 1 2 3 4 5
1  0  0  0  0  1 0 1 0 0 0 0
2  0  0  0  1  0 2 0 1 0 0 0 
......

每一行状态都由上一组状态推出，这里使用map进行计算

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(nums[0], map.getOrDefault(nums[0], 0) + 1);
        map.put(-nums[0], map.getOrDefault(-nums[0], 0) + 1);
        for (int i = 1; i < nums.length; i++) {
            int index = i;
            HashMap<Integer, Integer> t = map;
            HashMap<Integer, Integer> m = new HashMap<>();
            map.forEach((k, v) -> {
                m.put(k + nums[index], m.getOrDefault(k + nums[index], 0) + t.get(k));
                m.put(k - nums[index], m.getOrDefault(k - nums[index], 0) + t.get(k));
            });
            map = m;
        }
        return map.getOrDefault(target, 0);
    }
}