1
-
2
-
3
1
## 题目地址
2
+
4
3
https://leetcode.com/problems/target-sum/description/
5
4
6
5
## 题目描述
@@ -11,9 +10,9 @@ You are given a list of non-negative integers, a1, a2, ..., an, and a target, S.
11
10
Find out how many ways to assign symbols to make sum of integers equal to target S.
12
11
13
12
Example 1:
14
- Input: nums is [1, 1, 1, 1, 1], S is 3.
13
+ Input: nums is [1, 1, 1, 1, 1], S is 3.
15
14
Output: 5
16
- Explanation:
15
+ Explanation:
17
16
18
17
-1+1+1+1+1 = 3
19
18
+1-1+1+1+1 = 3
@@ -28,9 +27,10 @@ The sum of elements in the given array will not exceed 1000.
28
27
Your output answer is guaranteed to be fitted in a 32-bit integer.
29
28
30
29
```
30
+
31
31
## 思路
32
32
33
- 题目是给定一个数组,让你在数字前面添加 ` + ` 或者` - ` ,使其和等于target .
33
+ 题目是给定一个数组,让你在数字前面添加 ` + ` 或者` - ` ,使其和等于 target .
34
34
35
35
![ 494.target-sum] ( ../assets/problems/494.target-sum.png )
36
36
@@ -48,62 +48,22 @@ Your output answer is guaranteed to be fitted in a 32-bit integer.
48
48
49
49
![ 494.target-sum-3] ( ../assets/problems/494.target-sum-3.png )
50
50
51
- 因此问题转化为,求解` sumCount(nums, target) ` ,即nums数组中能够组成
52
- target的总数一共有多少种 ,这是一道我们之前做过的题目,使用动态规划可以解决。
51
+ 因此问题转化为,求解` sumCount(nums, target) ` ,即 nums 数组中能够组成
52
+ target 的总数一共有多少种 ,这是一道我们之前做过的题目,使用动态规划可以解决。
53
53
54
54
## 关键点解析
55
55
56
56
- 对元素进行分组,分组的依据是符号, 是` + ` 或者 ` - `
57
57
- 通过数学公式推导可以简化我们的求解过程,这需要一点` 数学知识和数学意识 `
58
58
59
59
## 代码
60
+
60
61
``` js
61
62
/*
62
63
* @lc app=leetcode id=494 lang=javascript
63
64
*
64
65
* [494] Target Sum
65
66
*
66
- * https://leetcode.com/problems/target-sum/description/
67
- *
68
- * algorithms
69
- * Medium (44.86%)
70
- * Total Accepted: 89.3K
71
- * Total Submissions: 198.5K
72
- * Testcase Example: '[1,1,1,1,1]\n3'
73
- *
74
- *
75
- * You are given a list of non-negative integers, a1, a2, ..., an, and a
76
- * target, S. Now you have 2 symbols + and -. For each integer, you should
77
- * choose one from + and - as its new symbol.
78
- *
79
- *
80
- * Find out how many ways to assign symbols to make sum of integers equal to
81
- * target S.
82
- *
83
- *
84
- * Example 1:
85
- *
86
- * Input: nums is [1, 1, 1, 1, 1], S is 3.
87
- * Output: 5
88
- * Explanation:
89
- *
90
- * -1+1+1+1+1 = 3
91
- * +1-1+1+1+1 = 3
92
- * +1+1-1+1+1 = 3
93
- * +1+1+1-1+1 = 3
94
- * +1+1+1+1-1 = 3
95
- *
96
- * There are 5 ways to assign symbols to make the sum of nums be target 3.
97
- *
98
- *
99
- *
100
- * Note:
101
- *
102
- * The length of the given array is positive and will not exceed 20.
103
- * The sum of elements in the given array will not exceed 1000.
104
- * Your output answer is guaranteed to be fitted in a 32-bit integer.
105
- *
106
- *
107
67
*/
108
68
// 这个是我们熟悉的问题了
109
69
// 我们这里需要求解的是nums里面有多少种可以组成target的方式
@@ -135,4 +95,4 @@ var findTargetSumWays = function(nums, S) {
135
95
136
96
## 扩展
137
97
138
- 如果这道题目并没有限定所有的元素以及target都是正数怎么办 ?
98
+ 如果这道题目并没有限定所有的元素以及 target 都是正数怎么办 ?
0 commit comments