您现在的位置是:首页 >其他 >LeetCode---494目标和网站首页其他
LeetCode---494目标和
简介LeetCode---494目标和
494. 目标和
给你一个整数数组 nums
和一个整数 target
。
向数组中的每个整数前添加 '+'
或 '-'
,然后串联起所有整数,可以构造一个 表达式 :
- 例如,
nums = [2, 1]
,可以在2
之前添加'+'
,在1
之前添加'-'
,然后串联起来得到表达式"+2-1"
。
返回可以通过上述方法构造的、运算结果等于 target
的不同 表达式 的数目。
示例 1:
输入: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:
输入:nums = [1], target = 1 输出:1
解析:01 背包问题:
1. 如何转化为01背包问题呢。
nums数组和为sum;
假设加法的总和为x,那么减法对应的总和就是sum - x。
所以我们要求的是 x - (sum - x) = target
x = (target + sum) / 2
2 .初始化dp[0]=1 ;因为不管成与不成,总会有一种情况。
3. 因为统计的是d
public int findTargetSumWays(int[] nums,int target){
int sum=0;
for (int i=0;i<nums.length;i++){
sum+=nums[i];
}
/**
不符合条件,凑不成target
*/
if ((target + sum) % 2 == 1){
return 0;
}
/**
* target大于sum
*/
if (Math.abs(target) > sum){
return 0;
}
//加法的总和为bagsize;
int bagsize=(sum + target) /2;
//确定dp
int[] dp=new int[bagsize + 1];
//初始化dp
dp[0]=1;
for (int i=0;i<nums.length;i++){
for (int j =bagsize ;j>=nums[i];j--){
dp[j]+=dp[j- nums[i]];//统计总和所以是加法;
}
}
return dp[bagsize];
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。