第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0494. 目标和

题目地址(494. 目标和)

题目描述

1
给定一个非负整数数组,a1, a2, ..., an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。
2
3
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
4
5
6
7
示例:
8
9
输入:nums: [1, 1, 1, 1, 1], S: 3
10
输出:5
11
解释:
12
13
-1+1+1+1+1 = 3
14
+1-1+1+1+1 = 3
15
+1+1-1+1+1 = 3
16
+1+1+1-1+1 = 3
17
+1+1+1+1-1 = 3
18
19
一共有5种方法让最终目标和为3。
20
21
22
提示:
23
24
数组非空,且长度不会超过 20 。
25
初始的数组的和不会超过 1000 。
26
保证返回的最终结果能被 32 位整数存下。
Copied!

前置知识

  • 动态规划

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

题目是给定一个数组,让你在数字前面添加 +或者-,使其和等于 target.
494.target-sum
暴力法的时间复杂度是指数级别的,因此我们不予考虑。我们需要换种思路.
我们将最终的结果分成两组,一组是我们添加了+的,一组是我们添加了-的。
494.target-sum-2
如上图,问题转化为如何求其中一组,我们不妨求前面标+的一组
如果求出一组,另一组实际就已知了,即总集和这一组的差集。
通过进一步分析,我们得到了这样的关系:
494.target-sum-3
因此问题转化为,求解sumCount(nums, target),即 nums 数组中能够组成 target 的总数一共有多少种,这是一道我们之前做过的题目,使用动态规划可以解决。

关键点解析

  • 对元素进行分组,分组的依据是符号, 是+ 或者 -
  • 通过数学公式推导可以简化我们的求解过程,这需要一点数学知识和数学意识

代码

1
/*
2
* @lc app=leetcode id=494 lang=javascript
3
*
4
* [494] Target Sum
5
*
6
*/
7
// 这个是我们熟悉的问题了
8
// 我们这里需要求解的是nums里面有多少种可以组成target的方式
9
var sumCount = function (nums, target) {
10
// 这里通过观察,我们没必要使用二维数组去存储这些计算结果
11
// 使用一维数组可以有效节省空间
12
const dp = Array(target + 1).fill(0);
13
dp[0] = 1;
14
for (let i = 0; i < nums.length; i++) {
15
for (let j = target; j >= nums[i]; j--) {
16
dp[j] += dp[j - nums[i]];
17
}
18
}
19
return dp[target];
20
};
21
const add = (nums) => nums.reduce((a, b) => (a += b), 0);
22
/**
23
* @param {number[]} nums
24
* @param {number} S
25
* @return {number}
26
*/
27
var findTargetSumWays = function (nums, S) {
28
const sum = add(nums);
29
if (sum < S) return 0;
30
if ((S + sum) % 2 === 1) return 0;
31
return sumCount(nums, (S + sum) >> 1);
32
};
Copied!
复杂度分析
  • 时间复杂度:$O(N * target)$
  • 空间复杂度:$O(target)$
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

扩展

如果这道题目并没有限定所有的元素以及 target 都是正数怎么办?