Medium

题目描述

给你一个下标从 0 开始的整数数组 nums 和一个整数 target。

返回和为 target 的 nums 的最长子序列的长度。如果不存在和为 target 的子序列，返回 -1。

子序列指的是从另一个数组中删除一些或者不删除元素而派生的数组，且剩余元素保持原来的顺序。

示例 1：

输入：nums = [1,2,3,4,5], target = 9
输出：3
解释：有 3 个和为 9 的子序列：[4,5]、[1,3,5] 和 [2,3,4]。最长的子序列是 [1,3,5] 和 [2,3,4]。因此答案是 3。

示例 2：

输入：nums = [4,1,3,2,1,5], target = 7
输出：4
解释：有 5 个和为 7 的子序列：[4,3]、[4,1,2]、[4,2,1]、[1,1,5] 和 [1,3,2,1]。最长的子序列是 [1,3,2,1]。因此答案是 4。

示例 3：

输入：nums = [1,1,5,4,5], target = 3
输出：-1
解释：可以证明 nums 没有和为 3 的子序列。

提示：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000
  • 1 <= target <= 1000

解题思路

这是一道经典的动态规划问题，类似于0-1背包问题，但求的是最长子序列长度而非最大价值。

思路分析：

我们可以使用动态规划来解决这个问题。定义 dp[i][j] 表示前 i 个元素中，和为 j 的最长子序列长度。

对于每个元素 nums[i-1]，我们有两种选择：

  1. 不选择当前元素：dp[i][j] = dp[i-1][j]
  2. 选择当前元素（前提是 j >= nums[i-1]）：dp[i][j] = dp[i-1][j-nums[i-1]] + 1

取两者的最大值作为 dp[i][j] 的值。

优化方案：

为了节省空间，我们可以使用一维数组进行状态压缩，从后往前更新以避免状态覆盖。初始化 dp[0] = 0（和为0的子序列长度为0），其他位置为 -1（表示不可达）。

最终答案就是 dp[target]，如果为 -1 说明无法构成和为 target 的子序列。

推荐解法： 使用一维动态规划进行空间优化，时间复杂度O(n×target)，空间复杂度O(target)。

代码实现

class Solution {
public:
    int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        vector<int> dp(target + 1, -1);
        dp[0] = 0;
        
        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                if (dp[j - num] != -1) {
                    dp[j] = max(dp[j], dp[j - num] + 1);
                }
            }
        }
        
        return dp[target];
    }
};

class Solution:
    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
        dp = [-1] * (target + 1)
        dp[0] = 0
        
        for num in nums:
            for j in range(target, num - 1, -1):
                if dp[j - num] != -1:
                    dp[j] = max(dp[j], dp[j - num] + 1)
        
        return dp[target]

public class Solution {
    public int LengthOfLongestSubsequence(IList<int> nums, int target) {
        int[] dp = new int[target + 1];
        Array.Fill(dp, -1);
        dp[0] = 0;
        
        foreach (int num in nums) {
            for (int j = target; j >= num; j--) {
                if (dp[j - num] != -1) {
                    dp[j] = Math.Max(dp[j], dp[j - num] + 1);
                }
            }
        }
        
        return dp[target];
    }
}

var lengthOfLongestSubsequence = function(nums, target) {
    const dp = new Array(target + 1).fill(-1);
    dp[0] = 0;
    
    for (const num of nums) {
        for (let j = target; j >= num; j--) {
            if (dp[j - num] !== -1) {
                dp[j] = Math.max(dp[j], dp[j - num] + 1);
            }
        }
    }
    
    return dp[target];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度分析
时间复杂度O(n × target)，其中 n 是数组长度，需要遍历每个元素和每个可能的和值
空间复杂度O(target)，使用一维数组存储状态

相关题目