【NO.92】 HOT 100—494. 目标和
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
文章目录
- 题目: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
提示:
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
解题
方式一:回溯
数组 nums的每个元素都可以添加符号 +或 -,因此每个元素有 2 种添加符号的方法,n个数共有 2^n种添加符号的方法,对应 2^n种不同的表达式。当 n 个元素都添加符号之后,即得到一种表达式,如果遍历完之后表达式的结果等于目标数 target,则该表达式即为符合要求的表达式。
可以使用回溯的方法遍历所有的表达式,回溯过程中维护一个计数器 count,当遇到一种表达式的结果等于目标数 target 时,将 count的值加 1。遍历完所有的表达式之后,即可得到结果等于目标数 target 的表达式的数目。
/**
* 时间复杂度:O(2^n)
* 空间复杂度:O(n),其中 n 是数组nums的长度。空间复杂度主要取决于递归调用的栈空间,栈的深度不超过 n。
*/
class Solution {
// 回溯法还是比较简单,好理解的
// + - 两种选择,可以看作是二叉树的左右节点,所以可以用深度优先遍历
// 遍历完如果sum==target,则 count++
int count = 0;
public int findTargetSumWays(int[] nums, int target) {
// 回溯过程,
backtrack(nums, target, 0, 0);
return count;
}
// 第三个参数为数组下标,第四个参数为目前的和
private void backtrack(int[] nums, int target, int index, int sum) {
if (index == nums.length) {
// 把所有数都算上后的结果
if (sum == target) {
count++;
}
} else {
backtrack(nums, target, index + 1, sum + nums[index]);
backtrack(nums, target, index + 1, sum - nums[index]);
}
}
}
方式二:动态规划
记数组的元素和为 sum,添加 -号的元素之和为 neg,则其余添加 +号 的元素之和为 sum−neg,得到的表达式的结果为(sum−neg)−neg=sum−2*neg=target,即:neg=(sum−target)/2。
由于数组 nums中的元素都是非负整数,则neg 也必须是非负整数,所以上式成立的前提是 sum−target是非负偶数。若不符合该条件可直接返回 0。
若上式成立,问题转化成在数组 nums中选取若干元素,使得这些元素之和等于neg,计算选取元素的方案数。我们可以使用动态规划的方法求解。
定义二维数组 dp,其中 dp[i][j] 表示在数组 nums的前 i 个数中选取元素,使得这些元素之和等于 j 的方案数。假设数组 nums的长度为 n,则最终答案为dp[n][neg]。
当没有任何元素可以选取时,元素和只能是 0,对应的方案数是 1,因此动态规划的边界条件是:
j=0时,dp[0][j] = 1
j≥1时,dp[0][j] = 0
之后来看i,
当 1≤i≤n时,对于数组 nums中的第 i个元素 num(i的计数从 1 开始),遍历 0≤j≤neg,计算 dp[i][j] 的值:
- 如果 j<num,则不能选 num(当前的数比我们的和还大,肯定不能选),此时有 dp[i][j]=dp[i−1][j]
- 如果 j≥num,则如果不选 num,方案数是 dp[i−1][j],如果选 num,方案数是 dp[i−1][j−num]。此时有 dp[i][j]=dp[i−1][j]+dp[i−1][j−num]
由此可以得到空间复杂度为 O(n×(sum-target)/2) 的实现。
这一段可以放在最后再看:(在动规划时,问题可以从从n个数字里找出和为neg的元素组合,转化为从n个物体中向最大负重为neg的背包里放东西的01背包问题,dp[i][j]表示取到第i个物品时,背包还剩j负重的组合数(本题中j肯定是非负整数),优化:由于到第i个物体时,其情况仅依赖第i-1的情况,与更之前的无关,采用使j递减的方式,减少dp数组在i的一个维度),后面可以再总结下背包相关问题。
/**
* 时间复杂度:O(2^n)
* 空间复杂度:O(n),其中 n 是数组nums的长度。空间复杂度主要取决于递归调用的栈空间,栈的深度不超过 n。
*/
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int num : nums) {
sum += num;
}
int diff = sum - target;
if (diff < 0 || diff % 2 != 0) {
return 0;
}
int n = nums.length, neg = diff / 2;
int[][] dp = new int[n + 1][neg + 1];
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
int num = nums[i - 1];
for (int j = 0; j <= neg; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= num) {
dp[i][j] += dp[i - 1][j - num];
}
}
}
return dp[n][neg];
}
}
由于 dp的每一行的计算只和上一行有关,因此可以使用滚动数组的方式,去掉 dp的第一个维度,将空间复杂度优化到 O(neg)。
实现时,内层循环需采用倒序遍历的方式,这种方式保证转移来的是 dp[i−1][]中的元素值。
/**
* 时间复杂度:O(n×(sum−target)),
* 空间复杂度:O(sum−target),
* 其中 n 是数组 nums的长度,sum\textit{sum}sum 是数组nums的元素和,target是目标数。
*/
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int num : nums) {
sum += num;
}
int diff = sum - target;
if (diff < 0 || diff % 2 != 0) {
return 0;
}
int neg = diff / 2;
int[] dp = new int[neg + 1];
dp[0] = 1;
for (int num : nums) {
for (int j = neg; j >= num; j--) {
dp[j] += dp[j - num];
}
}
return dp[neg];
}
}
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |