494.力扣每日一题6/30 Java(三种解法)

• 博客主页：音符犹如代码
• 系列专栏：算法练习
• 关注博主，后期持续更新系列文章
• 如果有错误感谢请大家批评指出，及时修改
• 感谢大家点赞👍收藏⭐评论✍

目录

思路

解题方法

时间复杂度

空间复杂度

Code

---

解法一：递归

思路

通过递归的方式遍历数组中的每个数字，对于每个数字，都有加上或减去两种选择。在递归过程中，当遍历完数组时，判断当前的总和是否等于目标值，如果相等则表示找到了一种满足条件的表达式组合。

解题方法

使用了深度优先搜索（DFS）的思想，通过递归地探索所有可能的符号组合来计算满足目标值的表达式数量。

时间复杂度

O(n²)

空间复杂度

O(n)

Code

import java.util.Arrays;
 
public class Solution {
 
    public int findTargetSumWays(int[] nums, int target) {
        return helper(nums, 0, target, 0);
    }
 
    public int helper(int[] nums, int index, int target, int currentSum) {
        if (index == nums.length) {
            if (currentSum == target) {
                return 1;
            }
            return 0;
        }
 
        int count = 0;
        count += helper(nums, index + 1, target, currentSum + nums[index]);
        count += helper(nums, index + 1, target, currentSum - nums[index]);
 
        return count;
    }
}
 

解法二：回溯法

思路

使用回溯法，通过递归地尝试对数组中的每个数字进行加和减的操作，来穷举所有可能的表达式组合。

解题方法

定义一个回溯函数backtrack，函数参数包括数组nums、当前处理的数字索引index、当前的总和currentSum以及目标值target。当index达到数组长度时，检查currentSum是否等于target，若相等则增加计数。否则，对于当前数字，分别进行加上和减去的操作，并递归调用自身处理下一个数字。

时间复杂度

𝑂(2*𝑛)

空间复杂度

O(n)

Code

public class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int totalCombinations = 1 << nums.length;
        int count = 0;
 
        for (int i = 0; i < totalCombinations; i++) {
            int sum = 0;
            for (int j = 0; j < nums.length; j++) {
                if ((i & (1 << j))!= 0) {
                    sum += nums[j];
                } else {
                    sum -= nums[j];
                }
            }
            if (sum == target) {
                count++;
            }
        }
        return count;
    }
}

解法三：动态规划

思路

首先计算数组元素的总和 sum 。如果目标值 target 的绝对值大于总和，或者 (target + sum) 不能被 2 整除，说明不存在满足条件的组合，直接返回 0 。然后将问题转化为找到一个子集，使得该子集元素之和为 (target + sum) / 2 ，通过计算这样的子集个数来得到满足目标和的表达式数量。

解题方法

使用动态规划，定义二维数组 dp[i][j] 表示处理到数组的第 i 个元素，和为 j 的不同表达式的数目。通过两层循环遍历数组和可能的和值，根据当前数字是否能加到当前和中更新 dp 值。

时间复杂度

O(n×m)

空间复杂度

O(n×m)

Code

public class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int totalCombinations = 1 << nums.length;
        int count = 0;
 
        for (int i = 0; i < totalCombinations; i++) {
            int sum = 0;
            for (int j = 0; j < nums.length; j++) {
                if ((i & (1 << j))!= 0) {
                    sum += nums[j];
                } else {
                    sum -= nums[j];
                }
            }
            if (sum == target) {
                count++;
            }
        }
        return count;
    }
}

一个人并不是生来要被打败的，你尽可以把他消灭掉，可就是打不败他。——《老人与海》