[LeetCode] 494. Target Sum 目标和
You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.
Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation: -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 There are 5 ways to assign symbols to make the sum of nums be target 3.
Note:
- The length of the given array is positive and will not exceed 20.
- The sum of elements in the given array will not exceed 1000.
- Your output answer is guaranteed to be fitted in a 32-bit integer.
这道题给了我们一个数组，和一个目标值，让给数组中每个数字加上正号或负号，然后求和要和目标值相等，求有多少中不同的情况。那么对于这种求多种情况的问题，博主最想到的方法使用递归来做。从第一个数字，调用递归函数，在递归函数中，分别对目标值进行加上当前数字调用递归，和减去当前数字调用递归，这样会涵盖所有情况，并且当所有数字遍历完成后，若目标值为0了，则结果 res 自增1，参见代码如下：
解法一：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int res = ;
helper(nums, S, , res);
return res;
}
void helper(vector<int>& nums, long S, int start, int& res) {
if (start >= nums.size()) {
if (S == ) ++res;
return;
}
helper(nums, S - nums[start], start + , res);
helper(nums, S + nums[start], start + , res);
}
};
我们对上面的递归方法进行优化，使用 memo 数组来记录中间值，这样可以避免重复运算，参见代码如下：
解法二：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
vector<unordered_map<int, int>> memo(nums.size());
return helper(nums, S, , memo);
}
int helper(vector<int>& nums, long sum, int start, vector<unordered_map<int, int>>& memo) {
if (start == nums.size()) return sum == ;
if (memo[start].count(sum)) return memo[start][sum];
int cnt1 = helper(nums, sum - nums[start], start + , memo);
int cnt2 = helper(nums, sum + nums[start], start + , memo);
return memo[start][sum] = cnt1 + cnt2;
}
};
我们也可以使用迭代的方法来解，使用一个 dp 数组，其中 dp[i][j] 表示到第 i-1 个数字且和为j的情况总数，参见代码如下：
解法三：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int n = nums.size();
vector<unordered_map<int, int>> dp(n + );
dp[][] = ;
for (int i = ; i < n; ++i) {
for (auto &a : dp[i]) {
int sum = a.first, cnt = a.second;
dp[i + ][sum + nums[i]] += cnt;
dp[i + ][sum - nums[i]] += cnt;
}
}
return dp[n][S];
}
};
我们也可以对上面的方法进行空间上的优化，只用一个 HashMap，而不是用一个数组的哈希表，在遍历数组中的每一个数字时，新建一个 HashMap，在遍历原 HashMap 中的项时更新这个新建的 HashMap，最后把新建的 HashMap 整个赋值为原 HashMap，参见代码如下：
解法四：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
unordered_map<int, int> dp;
dp[] = ;
for (int num : nums) {
unordered_map<int, int> t;
for (auto a : dp) {
int sum = a.first, cnt = a.second;
t[sum + num] += cnt;
t[sum - num] += cnt;
}
dp = t;
}
return dp[S];
}
};
Github 同步地址：
https://github.com/grandyang/leetcode/issues/494
类似题目：
参考资料：
https://leetcode.com/problems/target-sum/
https://leetcode.com/problems/target-sum/discuss/97371/Java-Short-DFS-Solution
https://leetcode.com/problems/target-sum/discuss/97369/Evolve-from-brute-force-to-dp
LeetCode All in One 题目讲解汇总(持续更新中...)
最新文章
- 解决绝对定位div position: absolute 后面的<a> Link不能点击
- Bash 中同名的内部命令和外部命令
- java Web应用配置log4j日志记录
- 《SDN核心技术剖析和实战指南》3.3读书笔记
- 浏览器兼容——DOM事件封装函数
- asp.net传值
- 【Android开发经验】Android举UI设计经验
- 推荐一本不错的书《Sencha Ext JS 5 Bootcamp in a Book》
- jenkins 解决构建成功后进程消失的问题
- scrapy爬虫框架和selenium的配合使用
- winform 所遇
- python简单实现tftp客户端（基于udp）
- 5336: [TJOI2018]party
- python---cookie模拟登陆和模拟session原理
- [转] Java 基础
- mysql乐观锁总结和实践（一）
- ASP.NET Web API 框架研究 Web Host模式路由及将请求转出到消息处理管道
- odoo方法
- 【Go命令教程】命令汇总
- Win7电脑开启局域网连接和共享过程中出现的"您可能没有权限使用网络资源"的解决办法