LintCode 1208. 目标和 JavaScript算法

本文主要是介绍LintCode 1208. 目标和 JavaScript算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

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

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

说明

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

样例

- 例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.- 例2:输入: nums 为 [], S 为 3. 
输出: 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算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---