【算法与数据结构】494、LeetCode目标和-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法与数据结构】494、LeetCode目标和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

【算法与数据结构】494、LeetCode目标和,算法,算法

二、解法

思路分析：本题和这道题【算法与数据结构】1049、LeetCode 最后一块石头的重量 II类似，同样可以转换成01背包问题。下面开始论述。假设添加正号的整数子集和为 $p os i t i v e$ ，添加负号的整数子集和为 $n e g a t i v e$ 。那么我们有 $p os i t i v e - n e g a t i v e = t a r g e t, p os i t i v e + n e g a t i v e = s u m$ 。因此 $p os i t i v e = (t a r g e t + s u m) /2$ ，其中 $s u m$ 代表nums的和。找到了和为 $p os i t i v e$ 的子集就找到了 $n e g a t i v e$ 。因此，问题变成了寻找和为 $p os i t i v e$ 的子集数量。寻找和为 $p os i t i v e$ 的子集是一个01背包问题。其中， $p os i t i v e$ 是背包的容量，物品及其价值是 $n u m s$ 数组。 $d p [j]$ 代表填满 $j$ （包括 $j$ ）这么大容积的包，有 $d p [j]$ 种方法。递归公式可以由 $d p [j - n u m s [i]]$ 得出，例如只要有 $n u m s [i]$ ，那么弄成 $d p [j]$ 的方法就有 $d p [j - n u m s [i]]$ 中，并且根据 $n u m s [i]$ 的不同会有不同的方法，所以 $d p [j]$ 应该采取累加的形式。然后 $d p [0]$ 应该初始化为1（为0的话所有的 $d p [j]$ 都是0）。

程序如下：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if ((target + sum) % 2 != 0 || abs(target) > sum) return 0;
        int positive = (target + sum) / 2;
        vector<int> dp(vector<int>(positive + 1, 0));
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {			// 遍历物品
            for (int j = positive; j >= nums[i]; j--) {			// 遍历背包容量
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[positive];
    }
};

复杂度分析：

时间复杂度： $O (m * n)$ ， n为nums数组大小，m为背包容量。
空间复杂度： $O (m)$ 。

三、完整代码

# include <iostream>
# include <vector>
# include <numeric>
using namespace std;

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if ((target + sum) % 2 != 0 || abs(target) > sum) return 0;
        int positive = (target + sum) / 2;
        vector<int> dp(vector<int>(positive + 1, 0));
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {			// 遍历物品
            for (int j = positive; j >= nums[i]; j--) {			// 遍历背包容量
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[positive];
    }
};

int main() {
    Solution s1;
    vector<int> nums = { 1,1,1,1,1 };
    int target = 3;
    int result = s1.findTargetSumWays(nums, target);
    cout << result << endl;
    system("pause");
    return 0;
}