LintCode 1208. 目标和 JavaScript算法

时间:2020-9-19 作者:admin

描述

给定一个非负整数的列表a1,a2,…an,再给定一个目标S。现在用+和-两种运算,对于每一个整数,选择一个作为它前面的符号。

找出有多少种方法,使得这些整数的和正好等于S。

说明

1、给定数组的长度是正整数而且不会超过20。
2、所有元素的和不会超过1000。
3、输出结果一定在32位整数范围内。

样例

-1:

输入: nums为 [1, 1, 1, 1, 1], S3. 
输出: 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 = 35种方法让和为3.

-2:

输入: nums 为 [], S3. 
输出: 0
解释: 
没有方法能让和为3

解析

var findTargetSumWays = function(nums, S) {
    if (nums == null || nums.length == 0) return 0;
    var sums = 0;
    nums.forEach(num => sums += num);
    if (sums < S || (S + sums) % 2 == 1) return 0;
    var p = (S + sums) >> 1;
    var dp = new Array(p + 1).fill(0);
    dp[0] = 1;
    nums.forEach(num => {
        for (var i = p; i >= num; i--) {
            dp[i] += dp[i - num];
        }
    })
    return dp[p];
};

运行结果

LintCode 1208. 目标和 JavaScript算法

LintCode 1208. 目标和 JavaScript算法

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。