class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
}
};
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 <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000相似题目
原站题解
cpp 解法, 执行用时: 3 ms, 内存消耗: 10.8 MB, 提交时间: 2024-06-30 22:41:05
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int s = reduce(nums.begin(), nums.end(), 0) - abs(target);
if (s < 0 || s % 2) {
return 0;
}
int m = s / 2; // 背包容量
vector<int> f(m + 1);
f[0] = 1;
for (int x : nums) {
for (int c = m; c >= x; c--) {
f[c] += f[c - x];
}
}
return f[m];
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 40.5 MB, 提交时间: 2024-06-30 22:40:50
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int s = 0;
for (int x : nums) {
s += x;
}
s -= Math.abs(target);
if (s < 0 || s % 2 == 1) {
return 0;
}
int m = s / 2; // 背包容量
int[] f = new int[m + 1];
f[0] = 1;
for (int x : nums) {
for (int c = m; c >= x; c--) {
f[c] += f[c - x];
}
}
return f[m];
}
}
python3 解法, 执行用时: 60 ms, 内存消耗: 15.9 MB, 提交时间: 2023-09-14 15:45:18
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
diff = sum(nums) - target
if diff < 0 or diff%2 == 1:
return 0
neg = diff // 2
dp = [0 for _ in range(neg+1)]
dp[0] = 1
for num in nums:
for j in range(neg, num-1, -1):
dp[j] += dp[j-num]
return dp[neg]
golang 解法, 执行用时: 0 ms, 内存消耗: 2.4 MB, 提交时间: 2021-06-07 14:54:27
func findTargetSumWays(nums []int, target int) int {
sum := 0
for _, v := range nums {
sum += v
}
diff := sum - target
if diff < 0 || diff%2 == 1 {
return 0
}
neg := diff/2
dp := make([]int, neg+1)
dp[0] = 1
for _, num := range nums {
for j := neg; j >= num; j-- {
dp[j] += dp[j-num]
}
}
return dp[neg]
}