当前位置: 首页 > >

2021-05-07:给定一个数组arr,你可以在每个数字之前决定+或者-,但是必须所有数字都参与 ,再给定一个数target,请问最后算出target的方法数是多少?

发布时间:

2021-05-07:给定一个数组arr,你可以在每个数字之前决定+或者-,但是必须所有数字都参与 ,再给定一个数target,请问最后算出target的方法数是多少?


福大大 答案2021-05-07:


优化点一 :
你可以认为arr中都是非负数
因为即便是arr中有负数,比如[3,-4,2]
因为你能在每个数前面用+或者-号
所以[3,-4,2]其实和[3,4,2]达成一样的效果
那么我们就全把arr变成非负数,不会影响结果的
优化点二 :
如果arr都是非负数,并且所有数的累加和是sum
那么如果target优化点三 :
因为题目要求一定要使用所有数字去拼target,
所以不管这些数字怎么用+和-折腾,最终的结果都一定不会改变奇偶性
所以,如果所有数的累加和是sum,
并且与target的奇偶性不一样,没有任何方法可以达到target,可以直接返回0
优化点四 :
比如说给定一个数组, arr = [1, 2, 3, 4, 5] 并且 target = 3
其中一个方案是 : +1 -2 +3 -4 +5 = 3
该方案中取了正的集合为P = {1,3,5}
该方案中取了负的集合为N = {2,4}
所以任何一种方案,都一定有 sum§ - sum(N) = target
现在我们来处理一下这个等式,把左右两边都加上sum§ + sum(N),那么就会变成如下:
sum§ - sum(N) + sum§ + sum(N) = target + sum§ + sum(N)
2 * sum§ = target + 数组所有数的累加和
sum§ = (target + 数组所有数的累加和) / 2
也就是说,任何一个集合,只要累加和是(target + 数组所有数的累加和) / 2
那么就一定对应一种target的方式
也就是说,比如非负数组arr,target = 7, 而所有数累加和是11
求使用所有数字的情况下,多少方法最后形成7?
其实就是求有多少个子集的累加和是9 -> (7 + 11) / 2
优化点五 :
二维动态规划的空间压缩技巧


代码用golang编写。代码如下:


package main

import "fmt"

func main() {
arr := []int{1, 1, 1, 1, 1}
target := 3
ret := findTargetSumWays3(arr, target)
fmt.Println(ret)
}

func findTargetSumWays3(arr []int, target int) int {
sum := 0
for _, n := range arr {
sum += n
}
return twoSelectOne(sum < target || ((target&1)^(sum&1)) != 0, 0, subset(arr, (target+sum)>>1))
}

func subset(nums []int, s int) int {
dp := make([]int, s+1)
dp[0] = 1
for _, n := range nums {
for i := s; i >= n; i-- {
dp[i] += dp[i-n]
}
}
return dp[s]
}

func twoSelectOne(condition bool, a int, b int) int {
if condition {
return a
} else {
return b
}
}

执行结果如下:



左神java代码



友情链接: