NC243. 目标和
描述
示例1
输入:
[1,1,1,2],3
输出:
3
说明:
-1 + 1 + 1 + 2 = 3示例2
输入:
[2],2
输出:
1
C++ 解法, 执行用时: 2ms, 内存消耗: 460KB, 提交时间: 2022-01-22
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @param target int整型
* @return int整型
*/
int findTargetSumWays(vector<int>& nums, int target) {
// write code here
if(!nums.size()) return 0;
int sum=0;
for(auto& num:nums)
sum+=num;
if((sum+target)%2) return 0;
target=(sum+target)/2;
vector<int> dp(target+1);
dp[0]=1;
for(int i=0;i<nums.size();i++){
for(int j=target;j>=nums[i];j--)
dp[j]+=dp[j-nums[i]];
}
return dp[target];
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2022-05-18
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @param target int整型
* @return int整型
*/
int findTargetSumWays(vector<int>& nums, int target) {
// write code here
if(nums.size() == 0)
return 0;
int sum = 0;
for(auto num: nums)
sum+=num;
if((sum+target)%2==1)
return 0;
int v = (sum+target)/2;
vector<vector<int>> dp(nums.size()+1,vector<int>(v+1,0));
dp[0][0] = 1;
for(int i =1; i<=nums.size(); ++i){
for(int j =0; j<=v; ++j){
dp[i][j] = dp[i-1][j];
if(j>=nums[i-1])
dp[i][j] += dp[i-1][j-nums[i-1]];
}
}
return dp[nums.size()][v];
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 420KB, 提交时间: 2022-05-24
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @param target int整型
* @return int整型
*/
int findTargetSumWays(vector<int>& nums, int target) {
// write code here
int sum=0;
if(nums.empty()) return 0;
for(auto n:nums) sum+=n;
int diff = sum-target;
if(diff%2 || diff<0) return 0;
vector<int> f(diff/2+1);
int neg = diff/2;
f[0]=1;
int n = nums.size();
for(int i=0;i<n;i++){
for(int j=neg;j>=nums[i];j--){
f[j]+=f[j-nums[i]];
}
}
return f[neg];
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 420KB, 提交时间: 2022-01-25
class Solution {
public:
/*
方法一：暴力递归
每一层递归可以选择对当前数添加或不添加负号，将其累加到结果上，直到凑出target
*/
int findTargetSumWays1(vector<int>& nums, int target) {
if (nums.size() == 0) return 0;
//return dfs_v1(nums, target, 0);
int res = 0; //保存结果
dfs_v2(nums, target, 0, 0, res);
return res;
}
/*
方法二：记忆化搜索（避免重复计算）
*/
int findTargetSumWays2(vector<int>& nums, int target) {
if (nums.size() == 0) return 0;
int n = nums.size();
map<int, map<int, int>> mem;
return dfs_mem(nums, target, mem, 0);
}
/*
方法三：动态规划 - 有BUG！
解题思路
本题可以转化为一个0-1背包问题。
我们将前面添加号的分为一组，记其累加和为a，将前面添减号的分为一组，记其累加和为b。
如果能构成一个表达式，使得结果为target，则有a+b=sum,a−b=target，其中sum为数组中所有数字的累加和。
继续化简一下，可以得到：a=(sum+target)/2。
如果数组中存在若干数字之和等于a，则对应其中一个合法的表达式等于target。
要想a存在，sum+target必为偶数。
状态定义：dp[i][j]dp[i][j]dp[i][j]表示i个元素时，有多少种不同的组合，其累加和为j。
状态初始化：初始化组成0的情况数为1。
状态转移：遍历nums数组中每一个数字，默认不选当前数字，即dp[i+1][j]=dp[i][j]。
如果j大于当前数字，则需要加上j−nums[i]时的组合数，即dp[i+1][j]+=dp[i][j−nums[i]]。
复杂度分析
时间复杂度：总共两次循环，需要执行n∗(V+1)次，所以时间复杂度是O(n∗V)。
空间复杂度：需要额外大小为(n+1)∗(V+1)的dp数组，所以空间复杂度为O(n∗V)。
参考：
https://blog.nowcoder.net/n/150a9cc1034148078a5686efed7158b4
*/
int findTargetSumWays(vector<int>& nums, int target) {
//边界情况判断
int n = nums.size();
if(n == 0) return 0;
//记录累加和
int sum = 0;
//遍历nums数组
for(int num:nums){
sum += num;
}
//计算背包容量
int V = (sum + target) / 2;
//如果为奇数，说明nums数组中找不打和为(sum+target)/2的若干数字
if((sum + target) % 2 == 1) return 0;
//dp[i][j]表示i个元素时，有多少种不同的组合，其累加和为j
//int dp[n+1][V+1];
vector<vector<int>> dp(n+1, vector<int>(V+1));
//初始化
dp[0][0]=1;
for(int i=0; i<n; i++){
for(int j=0; j<=V; j++){
//默认不选当前数字
dp[i+1][j] = dp[i][j];
//如果选择当前数字，则需要加上j-nums[i]时的组合数
if(j >= nums[i]){
dp[i+1][j] += dp[i][j-nums[i]];
}
}
}
return dp[n][V];
}
/*
动态规划解法优化
空间优化思路
由于方法一中，每次状态转移，只与上一行的状态有关，所以可以只使用一个维度构建dp数组。
每个数字只能选一次，所以需要倒序遍历背包容量，避免重复计算。
*/
int findTargetSumWays3(vector<int>& nums, int target) {
//边界情况判断
int n = nums.size();
if(n == 0) return 0;
//记录累加和
int sum = 0;
//遍历nums数组
for(int num:nums){
sum += num;
}
//计算背包容量
int V = (sum + target) / 2;
//如果为奇数，说明nums数组中找不打和为(sum+target)/2的若干数字
if((sum + target) % 2 == 1) return 0;
//dp[j]表示有多少种不同的组合，其累加和为j
vector<int> dp(V+1);
//初始化
dp[0]=1;
for(int i=0; i<nums.size(); i++){
//每个数字只选一次，所以需要倒序遍历，避免重复
for(int j=V; j>=nums[i]; j--){
dp[j] += dp[j-nums[i]];
}
}
return dp[V];
}
private:
//暴力递归调用
int dfs_v1(vector<int> nums, int rest, int index) {
// 到最后一个数如果rest为0了，就形成了一种合法的方案
if (index == nums.size()) {
if (rest == 0) return 1;
else return 0;
}
// 否则就给当前的数加上负号或不加负号累加到rest上，继续尝试下面的数
return dfs_v1(nums, rest + nums[index], index + 1) + dfs_v1(nums, rest - nums[index], index + 1);
}
void dfs_v2(vector<int> nums, int target, int index, int sum, int &count) {
if (index == nums.size() && sum == target) {
count += 1;
return;
}
if (index == nums.size()) return;
dfs_v2(nums, target, index + 1, sum + nums[index], count);
dfs_v2(nums, target, index + 1, sum - nums[index], count);
}
//记忆化搜索递归调用
int dfs_mem(vector<int> nums, int rest, map<int, map<int, int>> mem, int index) {
if (mem.find(index) != mem.end() && mem[index].find(rest) != mem[index].end()) {
mem[index][rest]; // 缓存命中，直接返回
}
if (index == nums.size()) // 到最后一个数如果rest为0了，就形成了一种合法的方案
return rest == 0 ? 1 : 0;
map<int, int> map;
// 否则就给当前的数加上负号或不加负号累加到rest上，继续尝试下面的数
int res = dfs_mem(nums, rest + nums[index], mem, index + 1) + dfs_mem(nums, rest - nums[index], mem, index + 1);
map[rest] = res;
mem[index] = map;
return res;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 424KB, 提交时间: 2022-04-01
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @param target int整型
* @return int整型
*/
int findTargetSumWays(vector<int>& nums, int target) {
// write code here
if(nums.size()==0) return 0;
int sum=0;
for(int i:nums){
sum+=i;
}
if((sum+target)%2==1) return 0;
if(sum<abs(target)) return 0;
target=(sum+target)/2;
vector<int> dp(target+1,0);
dp[0]=1;
for(int i=0;i<nums.size();i++){
for(int j=target;j>=nums[i];j--){
dp[j]+=dp[j-nums[i]];
}
}
return dp[target];
}
};