leetcode 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。

注意:

  1. 数组的长度不会超过20,并且数组中的值全为正数。
  2. 初始的数组的和不会超过1000。
  3. 保证返回的最终结果为32位整数。

题解

简单粗暴,直接根据上一次的结果存储各种可能性

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
func findTargetSumWays(nums []int, S int) int {
hash := make(map[int]int)
hash[0] = 1
for _, v := range nums {
tmp := make(map[int]int)
for k, _ := range hash {
tmp[k+v] += hash[k]
tmp[k-v] += hash[k]
}
hash = tmp
}
return hash[S]
}