Trace
6.7 每日一题
传送门：https://leetcode-cn.com/problems/target-sum/
Problem
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，
nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
1
2
3
4
5
6
7
8
| 输入：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：
1
2
| 输入：nums = [1], target = 1
输出：1
|
数据范围：
1
2
3
4
| 1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
|
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
int count=0;
void dfs(int k, vector<int>& nums, int target, int sum){
int a[2]={-1, 1};
if(k==nums.size()){
if(sum==target){
count++;
}
return ;
}
for(int i=0;i<2;i++){
sum=sum+nums[k]*a[i];
dfs(k+1, nums, target, sum);
sum=sum-nums[k]*a[i];
}
}
int findTargetSumWays(vector<int>& nums, int target) {
dfs(0, nums, target, 0);
return count;
}
};
|
时间复杂度$O(2^n)$，每次在倒数几个测试点TLE，应该是sum=sum+nums[k]*a[i]这被卡常了?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
int count=0;
void dfs(int k, vector<int>& nums, int target, int sum){
if(k==nums.size()){
if(sum==target){
count++;
}
return ;
}
dfs(k+1, nums, target, sum-nums[k]);
dfs(k+1, nums, target, sum+nums[k]);
}
int findTargetSumWays(vector<int>& nums, int target) {
dfs(0, nums, target, 0);
return count;
}
};
|
时间复杂度$O(2^n)$
空间复杂度$O(n)$
dp
将题目转化为$dp$题
记$nums$数组总和为$sum$，每给一个$nums[k]$前加'-'，表达式的值$ans=sum-2nums[k]$，假设所有加'-'的数字的和为$neg$，$ans=sum-2neg$，$ans==target$时满足条件。
反过来，从$nums$中找若干个数，和为$(sum-target)/2$，使其前面加'-'，即可满足条件。
$(sum-target)mod2!=0$时，不符合条件。
$(sum-target)<0$时，由于0 <= nums[i]，从中找不到若干个数，使其和为$(sum-target)/2$，不符合条件。
现在的问题变为，从$nums$中取若干数，使其和为$(sum-target)/2$，求方法数。
状态表示
dp[i][j]
集合：从前$i$个数中选，和为$j$的选法。
属性：选法总数。
状态转移
第$i$个数选不了，即nums[i]>j，dp[i][j]=dp[i-1][j]；
第$i$个数可以选，即nums[i]<=j ，dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]]
程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum=0;
for(int i=0;i<nums.size();i++){
sum+=nums[i];
}
int ans=sum-target;
if(ans%2) return 0;
if(ans<0) return 0;
ans/=2;
int f[21][2001];
f[0][0]=1;
for(int i=1;i<=nums.size();i++){
for(int j=0;j<=ans;j++){
f[i][j]=f[i-1][j];
if(nums[i-1]<=j){
f[i][j]+=f[i-1][j-nums[i-1]];
}
}
}
return f[nums.size()][ans];
}
};
|
时间复杂度：$O(n*ans)$
空间复杂度：$O(n*ans)$
空间复杂度还可以优化到$O(ans)$。
