您现在的位置是:首页 >其他 >LeetCode 494 目标和网站首页其他

LeetCode 494 目标和

yiyakaa 2024-06-17 11:25:09
简介LeetCode 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

思路:

用left记录正数,right记录负数
所以left+right=sum
left-right=target
推出left = (target+sum)/2
这里如果不能整除的话,也是没有答案的,直接返回0
并且如果目标值的绝对值大于sum时,不论怎么样都无法出不来taeget结果的
dp[j]表示:满容量为j时候,有dp[j]种方法
因此以上分析本题目满容量为left时,有dp[left]种方法
关于这种容量为多少,有dp多少种方法的题目
递推公式为dp[j]+=dp[j-nums[i]]
初始化也比较特殊,满容为0的时候有dp[0]种方法
dp[0]=1

class Solution {
public:
	int track(vector<int>& nums,int target) {
		int sum = 0;
		for (int i = 0; i < nums.size(); i++) {
			sum += nums[i];
		}
		vector<int> dp(10001,0);
		dp[0] = 1;
		if (abs(target) > sum)return 0;
		if ((target + sum) % 2 == 1)return 0;
		int maxtarget = (target + sum) / 2;
		for (int i = 0; i < nums.size();i++) {
			for (int j = maxtarget; j >= nums[i];j--) {
				dp[j] += dp[j - nums[i]];
			}
		}
		return dp[maxtarget];
	}
};

int main() {
	vector<int> nums = { 1, 1, 1, 1, 1 };
	int target = 3;
	Solution ss;
	cout<<ss.track(nums,target)<<endl;
	return 0;
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。