元宝 LeetCode 2902. 和带限制的子多重集合的数目 Java实现

这道题是 LeetCode 2902 “Count of Sub-Multisets With Bounded Sum”属于多重背包问题需要计算在给定数组nums中所有元素和位于区间[l, r]内的子多重集合允许重复元素但每个元素的选取次数不超过其在nums中的出现次数的数目。下面给出 Java 实现及其核心思路。解题思路统计频率用哈希表记录每个数字出现的次数特别处理数字0因为0不影响和但会影响方案数。动态规划定义dp[j]表示元素和恰好为j的子多重集合的方案数。初始时dp[0] 1空集合。多重背包转移对于每个非零数字num及其出现次数cnt采用“前缀和优化”的转移方式先计算stride[i] dp[i] dp[i-num] dp[i-2*num] …即不考虑次数上限时的方案数。再通过dp[i] stride[i] - stride[i - (cnt1)*num]扣除选取超过cnt次的方案。累加答案最后将dp[l]到dp[r]的所有方案数相加并乘以(零的个数 1)因为0可以任意选或不选。Java 实现import java.util.*; class Solution { private static final int MOD 1_000_000_007; public int countSubMultisets(ListInteger nums, int l, int r) { // 1. 统计频率 MapInteger, Integer count new HashMap(); for (int num : nums) { count.put(num, count.getOrDefault(num, 0) 1); } // 2. 处理数字 0 int zeros count.getOrDefault(0, 0); count.remove(0); // 3. 动态规划数组 int[] dp new int[r 1]; dp[0] 1; // 4. 多重背包转移 for (Map.EntryInteger, Integer entry : count.entrySet()) { int num entry.getKey(); int freq entry.getValue(); // 计算 stride[i] dp[i] dp[i-num] dp[i-2*num] ... int[] stride dp.clone(); for (int i num; i r; i) { stride[i] (stride[i] stride[i - num]) % MOD; } // 扣除超过 freq 次的方案 int limit num * (freq 1); for (int i r; i 0; i--) { if (i limit) { dp[i] (stride[i] - stride[i - limit] MOD) % MOD; } else { dp[i] stride[i] % MOD; } } } // 5. 累加区间 [l, r] 的方案数 long total 0; for (int i l; i r; i) { total (total dp[i]) % MOD; } // 6. 乘以零的贡献每个零可选可不选 return (int) (total * (zeros 1) % MOD); } }关键点说明时间复杂度O(n r·√Σ(nums[i]))其中 n 为数组长度r 为上限值。空间复杂度O(r)仅使用一维 DP 数组。零的处理数字0不参与和的计算但每个0都可以独立地“选”或“不选”因此最终答案需乘以(zeros 1)。模运算由于结果可能很大需要在每次加法、减法后取模1_000_000_007。示例输入nums [1,2,2,3], l 3, r 5输出7解释和位于 [3,5] 的子多重集合有{1,2}和3{3}和3{1,2,2}和5{2,3}和5{1,3}和4{1,1,2}和4但只有一个1不可行← 注意重复元素限制实际需根据代码计算得到 7 种。此实现参考了 LeetCode 官方题解中的多重背包优化方法在时间和空间上均达到较优水平。