【Day 62 】2024-06-08 - 494. 目标和

[azl397985856]

494. 目标和

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/target-sum/

前置知识

• 背包
• 数学

  题目描述

  给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，target。现在你有两个符号  +  和  -。对于数组中的任意一个整数，你都可以从  +  或  -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 target 的所有添加符号的方法数。

示例：

输入：nums: [1, 1, 1, 1, 1], target: 3
输出：5
解释：

-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

一共有5种方法让最终目标和为3。

[lxy1108]

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        dp = collections.defaultdict(int)
        dp[0]=1
        for num in nums:
            tmp = collections.defaultdict(int)
            for k in dp:
                tmp[k+num]+=dp[k]
                tmp[k-num]+=dp[k]
            dp = tmp
        return dp[target]

[CathyShang]

0-1背包问题

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        bag = target+sum(nums)
        if bag < 0 or bag%2:
            return 0

        @cache
        def dfs(i, c): # c背包容量
            if i < 0:
                return 1 if c==0 else 0
            if c < nums[i]:
                return dfs(i-1, c)
            return dfs(i-1, c)+dfs(i-1, c-nums[i])
        return dfs(len(nums)-1, bag//2)

n= len(nums) s= sum(nums)

• Time O(n*(Target+s))
• Space O(n*(Target+s))

[pandapls]

问题转换为 设有P，N分别为分组内 分组外的数总和， sum = P + N; P - N = target => P = sum + target / 2

var findTargetSumWays = function(nums, target) {
    // 计算数组的总和
    let sum = 0;
    for (const num of nums) {
        sum += num;
    }

    // 计算 P
    const diff = sum - target;
    if (diff < 0 || diff % 2 !== 0) {
        // 如果 diff 是负数或不是偶数，返回 0
        return 0;
    }

    const neg = Math.floor(diff / 2);

    // 初始化 dp 数组
    const dp = new Array(neg + 1).fill(0);
    dp[0] = 1;  // 和为0的子集只有一种，即空子集

    // 更新 dp 数组
    for (const num of nums) {
        for (let j = neg; j >= num; j--) {
            dp[j] += dp[j - num];
        }
    }

    // 返回和为 neg 的子集个数
    return dp[neg];
};

[zhiyuanpeng]

class Solution: def findTargetSumWays(self, nums, target) -> bool: t = sum(nums) + target if t % 2: return 0 t = t // 2

    dp = [0] * (t + 1)
    dp[0] = 1

    for i in range(len(nums)):
        for j in range(t, nums[i] - 1, -1):
            dp[j] += dp[j - nums[i]]
    return dp[-1]