DeepSeek LeetCode 494. 目标和 Java实现

LeetCode 494. 目标和 · Java 实现题意给定数组 nums 和目标值 target给每个数前加 或 -使表达式结果等于 target求方案数。思路一转化为 0-1 背包推荐设所有带 的数和为 P带 - 的数和为 N这里的 N 是绝对值则P - N target P N sum(nums)两式相加2P sum target即P (sum target) / 2于是问题转化为从 nums 中选若干个数使其和恰好为 P 的方案数这就是经典的 0-1 背包计数问题。边界判断· sum target 0 → 无解P 不能为负· (sum target) 为奇数 → 无解P 必须是整数· 也可以加 Math.abs(target) sum → 无解状态定义 dp[j] 表示和为 j 的方案数状态转移倒序遍历保证每个数只用一次dp[j] dp[j - num]classSolution{publicintfindTargetSumWays(int[]nums,inttarget){intsum0;for(intnum:nums)sumnum;// 边界判断intdiffsumtarget;if(diff0||diff%2!0)return0;intPdiff/2;int[]dpnewint[P1];dp[0]1;// 凑出 0 的方案只有 1 种一个都不选for(intnum:nums){// 0-1 背包必须倒序for(intjP;jnum;j--){dp[j]dp[j-num];}}returndp[P];}}复杂度· 时间O(n × P)其中 P (sum target) / 2· 空间O§思路二记忆化 DFS思路更直观从前往后依次给每个数决定 或 -用 (index, currentSum) 作为缓存键。classSolution{publicintfindTargetSumWays(int[]nums,inttarget){// key: index , curSumMapString,IntegermemonewHashMap();returndfs(nums,0,0,target,memo);}privateintdfs(int[]nums,inti,intcur,inttarget,MapString,Integermemo){if(inums.length){returncurtarget?1:0;}Stringkeyi,cur;Integercachedmemo.get(key);if(cached!null)returncached;intresdfs(nums,i1,curnums[i],target,memo)dfs(nums,i1,cur-nums[i],target,memo);memo.put(key,res);returnres;}}复杂度 时间 O(n × sum)空间 O(n × sum)记忆化状态数。如果不加记忆化纯 DFS 时间复杂度为 O(2^n)会 TLE。思路三二维 DP 写法便于理解转移过程dp[i][j] 表示用前 i 个数凑出和为 j 的方案数classSolution{publicintfindTargetSumWays(int[]nums,inttarget){intsum0;for(intnum:nums)sumnum;intdiffsumtarget;if(diff0||diff%2!0)return0;intPdiff/2;intnnums.length;int[][]dpnewint[n1][P1];dp[0][0]1;for(inti1;in;i){intnumnums[i-1];for(intj0;jP;j){dp[i][j]dp[i-1][j];// 不选 numif(jnum)dp[i][j]dp[i-1][j-num];// 选 num}}returndp[n][P];}}常见坑点 ⚠️(sum target) 可能为奇数或负数 —— 必须先判断否则 P 会出错。dp 数组不能写成 dp[0] 1, dp[num] 1 之类的简化初始化 —— 当 nums 中出现 0 时例如 [0,0,0,0,0]方案数会翻倍必须走标准背包转移。0-1 背包必须倒序遍历 j否则每个数会被重复使用等价于完全背包。答案不取模 —— 该题不使用 1e97因为题目保证结果在 int 范围内LeetCode 原题如此。推荐做法解法 时间 空间 推荐度0-1 背包一维 O(n·P) O§ ⭐⭐⭐⭐⭐记忆化 DFS O(n·sum) O(n·sum) ⭐⭐⭐⭐二维 DP O(n·P) O(n·P) ⭐⭐⭐面试首选一维背包解把P (sum target) / 2 的推导讲清楚就是加分项。