leetcode 494. 目标和 java
发布时间:2020-12-15 07:42:06 所属栏目:Java 来源:网络整理
导读:题目: 给定一个非负整数数组,a1,a2,...,an,和一个目标数,S。现在你有两个符号?+?和?-。对于数组中的任意一个整数,你都可以从?+?或?-中选择一个符号添加在前面。 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。 示例 1: 输入: nums: [1,1,1],S
题目:给定一个非负整数数组,a1,a2,...,an,和一个目标数,S。现在你有两个符号?+?和?-。对于数组中的任意一个整数,你都可以从?+?或?-中选择一个符号添加在前面。 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。 示例 1: 输入: nums: [1,1,1],S: 3 -1+1+1+1+1 = 3 一共有5种方法让最终目标和为3。 数组的长度不会超过20,并且数组中的值全为正数。 解题:class Solution { /** * 494 * 输入: nums: [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 * <p> * sum(P) 前面符号为+的集合;sum(N) 前面符号为减号的集合 * 所以题目可以转化为 * sum(P) - sum(N) = target * sum(nums) = sum(P) + sum(N) * => 2 * sum(P) = target + sum(nums) * => sum(P) = (target + sum(nums)) / 2 * 因此题目转化为01背包,也就是能组合成容量为sum(P)的方式有多少种 */ public static int findTargetSumWays(int[] nums,int S) { int sum = 0; for (int num : nums) { sum += num; } if (sum < S || (sum + S) % 2 == 1) { return 0; } int w = (sum + S) / 2; int[] dp = new int[w + 1]; dp[0] = 1; for (int num : nums) { for (int j = w; j >= num; j--) { dp[j] += dp[j - num]; } } return dp[w]; } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |