【LeetCode】目标和 Java 题解

关注

发布于: 2021 年 06 月 07 日

题目描述

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个表达式：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

示例 1：
输入：nums = [1,1,1,1,1], target = 3输出：5解释：一共有 5 种方法让最终目标和为 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+1 + 1 + 1 + 1 - 1 = 3
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/target-sum著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

仔细阅读题目，数组中数据只有两种符号，数据情况清晰，题目要求达成目标和的次数，使用回溯，模拟美剧情况，即可解决。

代码

class Solution {    int count = 0;
    public int findTargetSumWays(int[] nums, int S) {        backtrack(nums, S, 0, 0);        return count;    }
    public void backtrack (int[] nums, int target, int index, int sum) {        if (index == nums.length) {            if (sum == target) {                count++;            }        } else {            backtrack(nums, target, index + 1, sum + nums[index]);            backtrack(nums, target, index + 1, sum - nums[index]);        }    }}

复制代码

总结

上述回溯算法的时间复杂度是 O(2 ^ n), 空间复杂度是 O(n)
坚持每日一题，加油！

发布于: 2021 年 06 月 07 日阅读数: 10

原文链接:【http://xie.infoq.cn/article/e65af949b6ae755ecf28abdd9】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】目标和 Java 题解

题目描述

思路分析

代码

总结

HQ数字卡

评论