Java实现 LeetCode 494 目标和

Love The Way You Lie 2023-07-17 14:00 4阅读 0赞

## 494. 目标和 ##

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

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

示例 1:

输入: nums: \[1, 1, 1, 1, 1\], S: 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。  
注意:

数组非空，且长度不会超过20。  
初始的数组的和不会超过1000。  
保证返回的最终结果能被32位整数存下。

494
       输入: nums: [1, 1, 1, 1, 1], S: 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
      
      sum(P) 前面符号为+的集合；sum(N) 前面符号为减号的集合
      所以题目可以转化为
     sum(P) - sum(N) = target 
     => sum(nums) + sum(P) - sum(N) = target + sum(nums)
     => 2 * sum(P) = target + sum(nums) 
    => sum(P) = (target + sum(nums)) / 2
    因此题目转化为01背包，也就是能组合成容量为sum(P)的方式有多少种

class Solution { 
    
           public static int findTargetSumWays(int[] nums, int S) { 
            int sum = 0;
            for (int num : nums) { 
                sum += num;
            }
            if (sum < S || (sum + S) % 2 == 1) { 
                return 0;
            }
            int w = (sum + S) / 2;
            int[] dp = new int[w + 1];
            dp[0] = 1;
            for (int num : nums) { 
                for (int j = w; j >= num; j--) { 
                    dp[j] += dp[j - num];
                }
            }
            return dp[w];
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，4人围观）

还没有评论，来说两句吧...

相关阅读

相关 494.目标和

![在这里插入图片描述][67f4b8e3f6ed4ccd9f395c038504f144.png] 1. 回溯算法这题和之前做的那些排列、组合的回溯稍微有些不同，你

旧城等待，/ 2024年03月26日 13:41/ 0 赞/ 54 阅读

相关 LeetCode-494. 目标和

题目来源 [494. 目标和][494.] 思路 01背包问题是选或者不选，但本题是必须选，是选+还是选-。先将本问题转换为01背包问题。假设所有符号为+的

川长思鸟来/ 2024年03月25日 10:45/ 0 赞/ 58 阅读

相关 LeetCode - 494 目标和

目录题目来源题目描述示例提示题目解析算法源码 -------------------- 题目来源 [494. 目标和 - 力扣（LeetCod

左手的ㄟ右手/ 2023年09月26日 22:19/ 0 赞/ 110 阅读

相关 Java实现 LeetCode 494 目标和

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

Love The Way You Lie/ 2023年07月17日 14:00/ 0 赞/ 5 阅读

相关 Leetcode刷题java之494. 目标和

执行结果：通过显示详情执行用时 :515 ms, 在所有 Java 提交中击败了20.09% 的用户内存消耗 :34.2 MB, 在所有 Java 提交中击败了

分手后的思念是犯贱/ 2023年07月04日 11:11/ 0 赞/ 14 阅读

相关 494. 目标和

题目： [494. 目标和][494.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text

不念不忘少年蓝@/ 2022年12月02日 01:12/ 0 赞/ 113 阅读

相关 494. 目标和

给你一个整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个表达式：例如，nums =

向右看齐/ 2022年10月05日 10:59/ 0 赞/ 145 阅读

相关 494. 目标和

2021-06-07 LeetCode每日一题链接：[https://leetcode-cn.com/problems/target-sum/][https_leetc

谁践踏了优雅/ 2022年10月05日 06:59/ 0 赞/ 161 阅读

相关 leetcode 494. Target Sum | 494. 目标和（动态规划）

题目 [https://leetcode.com/problems/target-sum/][https_leetcode.com_problems_target-sum

「爱情、让人受尽委屈。」/ 2022年09月10日 14:24/ 0 赞/ 152 阅读

相关 leetcode 494 目标和

前言题目：[494. 目标和][494.] 参考题解：[494. 目标和][494. 1] -------------------- 提交代码这道题目挺难

怼烎@/ 2022年08月28日 04:57/ 0 赞/ 147 阅读