Medium

题目描述

给定一个大小为 n 的整数数组 nums 和一个正整数 k。

通过将每个元素 nums[i] 替换为 min(nums[i], x) 来获得由值 x 限制的数组。

对于从 1 到 n 的每个整数 x，确定是否可以从由 x 限制的数组中选择一个子序列，使得所选元素的和恰好为 k。

返回一个大小为 n 的 0 索引布尔数组 answer，其中 answer[i] 在使用 x = i + 1 时为 true（如果可能），否则为 false。

示例 1：

输入：nums = [4,3,2,4], k = 5
输出：[false,false,true,true]
解释：
- 对于 x = 1，限制后的数组是 [1, 1, 1, 1]。可能的和为 1, 2, 3, 4，所以无法形成和为 5。
- 对于 x = 2，限制后的数组是 [2, 2, 2, 2]。可能的和为 2, 4, 6, 8，所以无法形成和为 5。
- 对于 x = 3，限制后的数组是 [3, 3, 2, 3]。子序列 [2, 3] 的和为 5，所以是可能的。
- 对于 x = 4，限制后的数组是 [4, 3, 2, 4]。子序列 [3, 2] 的和为 5，所以是可能的。

示例 2：

输入：nums = [1,2,3,4,5], k = 3
输出：[true,true,true,true,true]
解释：对于每个 x 值，总是可以从限制后的数组中选择一个和恰好为 3 的子序列。

约束条件：

  • 1 <= n == nums.length <= 4000
  • 1 <= nums[i] <= n
  • 1 <= k <= 4000

解题思路

这道题的关键在于理解限制操作的本质和优化动态规划的计算。

核心思路：

  1. 排序优化：将数组按降序排列。这样对于限制值 x，所有大于 x 的元素都在数组前部，可以统一处理。

  2. 动态规划状态设计：使用 dp[i][sum] 表示从索引 i 到数组末尾是否可以选择子序列使和为 sum。

  3. 限制操作的等价转换：对于限制值 x，将所有大于 x 的元素都变为 x。设有 t 个元素大于 x，那么这 t 个元素可以选择 0 到 t 个，每个贡献值为 x。

  4. 分层计算：

    • 首先计算原数组（不限制的情况下）的 DP 表
    • 对于每个限制值 x，找到有多少个元素 t 大于 x
    • 枚举所有可能的「原始部分和」s（来自索引 t 之后的元素）
    • 枚举选择多少个被限制的元素 m（0 ≤ m ≤ t）
    • 检查是否存在 s + m × x = k

优化点：

  • 通过排序避免重复计算
  • 利用 DP 表的递推性质减少状态转移
  • 预计算可达和的集合，避免不必要的枚举

这种方法将时间复杂度控制在 O(n²k) 范围内，适合题目的约束条件。

代码实现

class Solution {
public:
    vector<bool> subsequenceSumAfterCapping(vector<int>& nums, int k) {
        int n = nums.size();
        sort(nums.rbegin(), nums.rend()); // 降序排列
        
        // dp[i][sum] = true 表示从索引i到末尾可以选择子序列使和为sum
        vector<vector<bool>> dp(n + 1, vector<bool>(k + 1, false));
        dp[n][0] = true;
        
        // 从后往前填充DP表
        for (int i = n - 1; i >= 0; i--) {
            for (int sum = 0; sum <= k; sum++) {
                dp[i][sum] = dp[i + 1][sum]; // 不选当前元素
                if (sum >= nums[i]) {
                    dp[i][sum] = dp[i][sum] || dp[i + 1][sum - nums[i]]; // 选择当前元素
                }
            }
        }
        
        vector<bool> answer(n);
        
        for (int x = 1; x <= n; x++) {
            // 找到第一个 <= x 的位置
            int t = 0;
            while (t < n && nums[t] > x) {
                t++;
            }
            
            // 检查是否可能达到和k
            for (int sum = 0; sum <= k; sum++) {
                if (dp[t][sum]) {
                    int remaining = k - sum;
                    if (remaining >= 0 && remaining % x == 0 && remaining / x <= t) {
                        answer[x - 1] = true;
                        break;
                    }
                }
            }
        }
        
        return answer;
    }
};

class Solution:
    def subsequenceSumAfterCapping(self, nums: List[int], k: int) -> List[bool]:
        n = len(nums)
        nums.sort(reverse=True)  # 降序排列
        
        # dp[i][sum] = True 表示从索引i到末尾可以选择子序列使和为sum
        dp = [[False] * (k + 1) for _ in range(n + 1)]
        dp[n][0] = True
        
        # 从后往前填充DP表
        for i in range(n - 1, -1, -1):
            for sum_val in range(k + 1):
                dp[i][sum_val] = dp[i + 1][sum_val]  # 不选当前元素
                if sum_val >= nums[i]:
                    dp[i][sum_val] = dp[i][sum_val] or dp[i + 1][sum_val - nums[i]]  # 选择当前元素
        
        answer = [False] * n
        
        for x in range(1, n + 1):
            # 找到第一个 <= x 的位置
            t = 0
            while t < n and nums[t] > x:
                t += 1
            
            # 检查是否可能达到和k
            for sum_val in range(k + 1):
                if dp[t][sum_val]:
                    remaining = k - sum_val
                    if remaining >= 0 and remaining % x == 0 and remaining // x <= t:
                        answer[x - 1] = True
                        break
        
        return answer

public class Solution {
    public bool[] SubsequenceSumAfterCapping(int[] nums, int k) {
        int n = nums.Length;
        Array.Sort(nums, (a, b) => b.CompareTo(a)); // 降序排列
        
        // dp[i,sum] = true 表示从索引i到末尾可以选择子序列使和为sum
        bool[,] dp = new bool[n + 1, k + 1];
        dp[n, 0] = true;
        
        // 从后往前填充DP表
        for (int i = n - 1; i >= 0; i--) {
            for (int sum = 0; sum <= k; sum++) {
                dp[i, sum] = dp[i + 1, sum]; // 不选当前元素
                if (sum >= nums[i]) {
                    dp[i, sum] = dp[i, sum] || dp[i + 1, sum - nums[i]]; // 选择当前元素
                }
            }
        }
        
        bool[] answer = new bool[n];
        
        for (int x = 1; x <= n; x++) {
            // 找到第一个 <= x 的位置
            int t = 0;
            while (t < n && nums[t] > x) {
                t++;
            }
            
            // 检查是否可能达到和k
            for (int sum = 0; sum <= k; sum++) {
                if (dp[t, sum]) {
                    int remaining = k - sum;
                    if (remaining >= 0 && remaining % x == 0 && remaining / x <= t) {
                        answer[x - 1] = true;
                        break;
                    }
                }
            }
        }
        
        return answer;
    }
}

var subsequenceSumAfterCapping = function(nums, k) {
    const n = nums.length;
    const answer = new Array(n);
    
    for (let x = 1; x <= n; x++) {
        const capped = nums.map(num => Math.min(num, x));
        const dp = new Array(k + 1).fill(false);
        dp[0] = true;
        
        for (const val of capped) {
            for (let sum = k; sum >= val; sum--) {
                if (dp[sum - val]) {
                    dp[sum] = true;
                }
            }
        }
        
        answer[x - 1] = dp[k];
    }
    
    return answer;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n²k)
空间复杂度O(nk)

详细说明：

  • 时间复杂度：排序 O(n log n)，构建 DP 表 O(nk)，对每个限制值 x 查询 O(nk)，总共 O(n²k)
  • 空间复杂度：DP 表占用 O(nk) 空间，其他辅助空间为 O(n)