LEETCODE 494. Target Sum

题目大意：

目标和

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例 1:

输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释:

-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

一共有5种方法让最终目标和为3。
注意:

数组的长度不会超过20，并且数组中的值全为正数。
初始的数组的和不会超过1000。
保证返回的最终结果为32位整数。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=494

解题思路分析：

这是一道中等难度的题目，传说暴力解也可以过，不过这里还是讲下如何使用DP的方法来解题。

其实刚看到题目后并没有想到，原来本题与 LEETCODE 416. PARTITION EQUAL SUBSET SUM解题思路分析 居然是一个思路。这个思路的变换十分巧妙，我们具体来分析一下。

首先，我们要为数组中的数加上加号或者减号，换句话说，我们可以将数组的数分成两部分，一部分是正数，一部分是负数，并且他们的和要满足等于目标数S。我们用sum[p]代表所有添加加号数字之和，sum[n]代表添加减号数字之和，即：

sum[p] - sum[n] = S;

另外，sum[p]与sum[n]是由原数组nums[]拆分所得，因此：

sum[p] - sum[n] = S;
sum[p] + sum[n] = sum[nums];

有了上面两个公式，我们将其合并一下，看看有什么惊喜呢？

sum[p] - sum[n] = S;
sum[p] + sum[n] = sum[nums];

// 合并上面两个公式
sum[p] - sum[n] + sum[p] + sum[n] = S + sum[nums];
2 * sum[p] = S + sum[nums];
sum[p] = (S + sum[nums]) / 2;

到此，我们得到了一个结论，就是，我们能不能在原数组nums[]中找到一些数字，并且他们的和能够等于(S + sum[nums]) / 2。其中(S + sum[nums]) / 2都是题目中的已知数，我们可以算出一个常量，称之为target。另外这里可以做一个处理，如果(S + sum[nums]) / 2不是整数，那么说明一定不存在解，可以直接返回0。到此，问题就完全转化成为 LEETCODE 416. PARTITION EQUAL SUBSET SUM解题思路分析 的求解方式。我们看下代码：

// sum[p] + sum[n] = sum[nums];
// sum[p] - sum[n] = S;
// 2sum[p] = sum[nums] + S
// sum[p] = (sum[nums] +S) / 2
public int findTargetSumWays(int[] nums, int S) {
    // 求出所有数的和
    int sum = 0;
    for (int n : nums) {
        sum += n;
    }
    // 如果和小于S，说明无法得到解，返回false。（注意S有可能为负）
    if (S > 0 && sum < S || S < 0 && -sum > S) {
        return 0;
    }
    // 如果计算出的target不是整数，返回false。
    if ((sum + S) % 2 != 0) {
        return 0;
    }
    // 根据推导公式，计算出target
    int target = (sum + S) / 2;
    // dp数组。
    // dp[i]表示在原数组中找出一些数字，并且他们的和为下标i的可能有多少种。
    int[] dp = new int[target + 1];
    // 初始化dp[0]为1
    dp[0] = 1;
    // 循环数组中所有数字
    for (int n : nums) {
        // 从0循环到target - n。
        for (int i = target - n; i >= 0; i--) {
            // dp[i]大于0说明，存在dp[i]种组合，其和为i的可能性
            if (dp[i] > 0) {
                // 既然存在和为i的可能，那么i加上当前数字的和也是存在的
                dp[i + n] += dp[i];
            }
        }
    }
    return dp[target];
}

本解法用时2ms。

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-494-target-sum/