企业官网建设流程全解析

LeetCode 494：目标和（Target Sum）—— 题解 ✅

🔗 题目链接

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

📖 内容概要

给定一个非负整数数组nums和一个整数target，
你可以在每个数字前加+或-，使计算结果等于target。
返回所有可能的表达式数量。

✅ 0/1 背包（计数问题）
✅ 数学转化是关键
✅ 面试高频题

💡 解题思路（核心）

一、关键数学转化（非常重要）

设：

• 正数和为P
• 负数绝对值和为N

则有：

P - N = target P + N = sum

解得：

P = (sum + target) / 2

👉问题转化为：

从数组中选出若干数，使其和正好等于P

二、不可行的情况（剪枝）

if((sum+target)%2==1)return0;if(Math.abs(target)>sum)return0;

三、DP 定义

dp[j]=和为 j 的方案数

四、状态转移方程

dp[j]+=dp[j-nums[i]];

✅ 每个数只能用一次
✅ 倒序遍历（0/1 背包）

五、初始化

dp[0]=1;

什么都不选，是一种方案

✅ AC 代码（Java）

classSolution{publicintfindTargetSumWays(int[]nums,inttarget){intsum=0;for(inta:nums){sum+=a;}intleft=(sum+target)/2;// 剪枝if((sum+target)%2==1)return0;if(Math.abs(target)>sum)return0;int[]dp=newint[left+1];dp[0]=1;// 0/1 背包（计数）for(inti=0;i<nums.length;i++){for(intj=left;j>=nums[i];j--){dp[j]+=dp[j-nums[i]];}}returndp[left];}}

⏱️ 复杂度分析

🔍 与 416 / 1049 的对比

✅ 三题本质都是子集和问题
✅ 区别在于 DP 含义不同

✅ 一句话总结

把“加减符号问题”转化为“子集和为 P 的方案数问题”，再用 0/1 背包计数。

📌 面试加分点（建议记住）

• ✅ 为什么是(sum + target) / 2
• ✅ 为什么dp[0] = 1
• ✅ 为什么是+=而不是max
• ✅ 与回溯法的对比（会超时）