专栏首页健程之道力扣494——目标和

力扣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位整数存下。

原题url:https://leetcode-cn.com/problems/target-sum/

解题

简单递归

最简单的方法就是计算出所有的可能性,如果最终结果等于目标值,则说明该情况可以。直接看一下代码:

public class Solution {

    int result = 0;

    public int findTargetSumWays(int[] nums, int S) {
        // 递归
        findTargetSumWays(nums, S, 0, 0);
        // 返回最终结果
        return result;
    }

    // index : 当前计算到数组中的位置
    // sum : 当前的总和
    public void findTargetSumWays(int[] nums, int S, int index, int sum) {
        // 遍历是否结束
        if (index == nums.length) {
            // 如果总和等于S,则最终结果+1
            if (sum == S) {
                result++;
            }
            return;
        }

        // 针对当前的数值,有加和减两种情况
        findTargetSumWays(nums, S, index + 1, sum + nums[index]);
        findTargetSumWays(nums, S, index + 1, sum - nums[index]);
    }
}

方法很简单,但是时间复杂度太高,O(2^n),执行用时在 java 中也只打败了31.65%,看来确实不够好。

简单的动态规划

这其实类似于背包问题,有容量要求(部分数字之和等于目标值)。首先我们来想一下状态转移方程:

我们用二维数组dp[i][j]表示用数组中的前i个元素,组成和为j的方案数。考虑第i个数nums[i],它可以被添加 + 或 -,因此状态转移方程如下:

dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]]

也可以写成递推的形式:

dp[i][j + nums[i]] += dp[i - 1][j]
dp[i][j - nums[i]] += dp[i - 1][j]

因为题目中提到所有数的和不超过 1000,那么 j 的最小值可以达到 -1000。在 java 中,是不允许数组的下标为负数的,因此我们需要给dp[i][j]的第二维预先增加 1000,那么新的递推关系如下:

dp[i][j + nums[i] + 1000] += dp[i - 1][j + 1000]
dp[i][j - nums[i] + 1000] += dp[i - 1][j + 1000]

接下来我们看看代码:

public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        if (S > 1000 || S < -1000) {
            return 0;
        }

        // 求和的最大值
        int max = 1000;
        // 初始的数组的和不会超过1000,因此最大为1000,最小为-1000
        int[][] dp = new int[nums.length][max * 2 + 1];
        // 针对nums[0],先求出第一步
        dp[0][nums[0] + max] = 1;
        dp[0][-nums[0] + max] += 1;
        // 遍历数组
        for (int i = 1; i < nums.length; i++) {
            for (int sum = -max; sum <= max; sum++) {
                // 如果上一步有求出和为sum,那么可以继续计算下一步
                if (dp[i - 1][sum + max] > 0) {
                    dp[i][nums[i] + sum + max] += dp[i - 1][sum + max];
                    dp[i][-nums[i] + sum + max] += dp[i - 1][sum + max];
                }
            }
        }

        return dp[nums.length - 1][S + max];
    }
}

提交OK,时间复杂度为O(N ∗ max),max 代表数组中所有数字之和的最大值,执行用时在 java 中打败了58.91%,看来还有很大的提升空间。

动态规划 + 找规律

我们想一下,之所以上面的方法会涉及到 max,因为所谓的求和,并不只是加法,也可以用减法。这和我们一般理解的背包问题还是有所不同的,那么我们是否可以将本题转换成真正意义上的背包问题呢?

首先,我们可以将这组数看成两部分,P 和 N,其中 P 使用正号,N 使用负号,那么可以推导出一下关系:

1、target = sum(P) - sum(N)
2、sum(nums) = sum(P) + sum(N)
由1可以得出:sum(P) = target + sum(N)
由2可以得出:sum(N) = sum(nums) - sum(P)
综合以上,可以得出:
sum(P) = (target + sum(nums)) / 2

因此只要找到一个子集,令它们都取正号,并且和等于 (target + sum(nums))/2,就证明存在解,这就属于正常的0-1背包问题的范畴了。需要注意target + sum(nums)必须为偶数,否则 sum(P) 就是小数了,这和题目要求的所有数都是非负整数不符。

接下来我们看看代码:

public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        if (S > 1000 || S < -1000) {
            return 0;
        }
        // 求出数组的和
        int sumNums = 0;
        for (int num : nums) {
            sumNums += num;
        }
        // 新的目标和(sumNums + S) / 2
        int newTarget = sumNums + S;
        // 如果是奇数,那么无法被2整除,不符合规则
        if ((newTarget & 1) == 1) {
            return 0;
        }
        newTarget = newTarget / 2;

        // 正常的背包问题,在nums中找几个数,满足和为newTarget
        // dp[i]表示从数组nums找出和为i的组合情况
        int[] dp = new int[newTarget + 1];
        dp[0] = 1;
        // 遍历数组
        for (int num : nums) {
            // 更新dp
            for (int sum = newTarget; sum >= num; sum--) {
                dp[sum] += dp[sum - num];
            }
        }

        return dp[newTarget];
    }
}
提交OK,时间复杂度是`O(n * newTarget)`,其中,` newTarget = (target + sum(nums))/2`,和前面方法中的`max`相比,`sum(nums) <= max`,如果`target > max`,也会直接返回0,因此这个方法的时间复杂度更优。

## 总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题主要是利用动态规划,优化时可以找规律,转化成正常的背包问题

有兴趣的话可以访问我的博客或者关注我的公众号、头条号,说不定会有意外的惊喜。

https://death00.github.io/

本文分享自微信公众号 - 健程之道(JianJianCoder),作者:健健壮

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 力扣560——和为K的子数组

    给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。

    健程之道
  • 力扣416——分割等和子集

    这道题主要涉及的是动态规划,类似背包问题,主要还是需要找出状态转移方程,优化时可以考虑采用深度优先搜索。

    健程之道
  • 力扣198——打家劫舍

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小...

    健程之道
  • Leetcode724:寻找数组的中心索引(java、python3)

    给定一个整数类型的数组 `nums`,请编写一个能够返回数组**“中心索引”**的方法。

    爱写bug
  • Leetcode724:寻找数组的中心索引(java、python3)

    我们是这样定义数组中心索引的:数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。

    爱写bug
  • Leetcode-Medium 494. Target Sum

    给定一个非负整数序列,a1, a2, …, an,和一个目标值 S。现在你有两种符号 + 和 -。对于每个整数,你可以选择为其选择一个符号。找到有多少种添加符号...

    致Great
  • LeetCode - 删除链表中的节点 & 移动零

    鉴于这次的两题,异常的短,所以再次合二为一。分别是第237,难度简单,以及283题,难度同样简单。

    晓痴
  • 冒泡排序

        public static void main(String[] args) {         //定义10个数字数组         int[]...

    用户2192970
  • 每日算法系列【LeetCode 239】滑动窗口最大值

    给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

    godweiyang
  • LeetCode53-Maximum Subarray

    tags : Divide And Conquer Dynamic Programming Array

    Dylan Liu

扫码关注云+社区

领取腾讯云代金券