Hard

题目描述

给你一个由非负整数组成的下标从 0 开始的数组 nums，以及两个整数 l 和 r。

返回 nums 中元素和在闭区间 [l, r] 内的子多重集的数目。

由于答案可能很大，请将其对 10^9 + 7 取模后返回。

子多重集是数组中元素的一个无序集合，其中给定值 x 可以出现 0, 1, …, occ[x] 次，其中 occ[x] 是 x 在数组中的出现次数。

注意：

  • 如果两个子多重集在排序后得到相同的多重集，则认为它们是相同的。
  • 空多重集的和为 0。

示例 1：

输入：nums = [1,2,2,3], l = 6, r = 6
输出：1
解释：nums 中和为 6 的唯一子集是 {1, 2, 3}。

示例 2：

输入：nums = [2,1,4,2,7], l = 1, r = 5
输出：7
解释：nums 中和在范围 [1, 5] 内的子集有 {1}, {2}, {4}, {2, 2}, {1, 2}, {1, 4}, {1, 2, 2}。

示例 3：

输入：nums = [1,2,1,3,5,2], l = 3, r = 5
输出：9
解释：nums 中和在范围 [3, 5] 内的子集有 {3}, {5}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {1, 1, 2}, {1, 1, 3}, {1, 2, 2}。

提示：

  • 1 <= nums.length <= 2 * 10^4
  • 0 <= nums[i] <= 2 * 10^4
  • nums 的元素和不超过 2 * 10^4
  • 0 <= l <= r <= 2 * 10^4

解题思路

这道题是经典的多重背包问题的变种。我们需要计算所有可能子多重集的和，然后统计在 [l, r] 范围内的数量。

核心思路：

  1. 统计频次：首先统计每个数值的出现次数，因为相同数值可以选择多次。

  2. 动态规划：使用 dp[sum] 表示能组成和为 sum 的子多重集数量。初始化 dp[0] = 1（空集）。

  3. 多重背包处理：对每个不同的数值 num，如果它出现 count 次，我们需要考虑选择 0, 1, 2, …, count 个该数值的所有可能。

  4. 滑动窗口优化：直接的三层循环会超时。关键优化是使用滑动窗口技术：

    • 对于数值 num，将所有和按照对 num 取模分组
    • 在每个余数类中，使用滑动窗口维护最多 count 个连续元素的和

  5. 特殊处理0：如果数组中有0，由于0不改变和值，含有 k 个0的方案数需要乘以选择0的方案数。

算法流程：

  • 统计每个数值的频次
  • 对于每个非零数值，使用滑动窗口优化的多重背包DP
  • 对于数值0，最后统一处理其贡献
  • 累加 dp[l] 到 dp[r] 的结果

时间复杂度主要由DP转移决定，滑动窗口优化后可以达到较好的性能。

代码实现

class Solution {
public:
    int countSubMultisets(vector<int>& nums, int l, int r) {
        const int MOD = 1e9 + 7;
        unordered_map<int, int> count;
        int total = 0;
        
        for (int num : nums) {
            count[num]++;
            total += num;
        }
        
        vector<long long> dp(r + 1, 0);
        dp[0] = 1;
        
        int zeros = count[0];
        count.erase(0);
        
        for (auto& [num, cnt] : count) {
            for (int remainder = 0; remainder < num; remainder++) {
                vector<long long> vals;
                int sum = 0;
                
                for (int val = remainder; val <= r; val += num) {
                    vals.push_back(dp[val]);
                    sum = (sum + dp[val]) % MOD;
                }
                
                for (int i = 0; i < vals.size(); i++) {
                    int val = remainder + i * num;
                    if (i >= cnt + 1) {
                        sum = (sum - vals[i - cnt - 1] + MOD) % MOD;
                    }
                    dp[val] = sum;
                }
            }
        }
        
        long long result = 0;
        for (int i = l; i <= r; i++) {
            result = (result + dp[i]) % MOD;
        }
        
        return (result * (zeros + 1)) % MOD;
    }
};

class Solution:
    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:
        MOD = 10**9 + 7
        count = {}
        
        for num in nums:
            count[num] = count.get(num, 0) + 1
        
        dp = [0] * (r + 1)
        dp[0] = 1
        
        zeros = count.get(0, 0)
        if 0 in count:
            del count[0]
        
        for num, cnt in count.items():
            for remainder in range(num):
                vals = []
                total = 0
                
                for val in range(remainder, r + 1, num):
                    vals.append(dp[val])
                    total = (total + dp[val]) % MOD
                
                for i in range(len(vals)):
                    val = remainder + i * num
                    if i >= cnt + 1:
                        total = (total - vals[i - cnt - 1]) % MOD
                    dp[val] = total
        
        result = sum(dp[l:r+1]) % MOD
        return (result * (zeros + 1)) % MOD

public class Solution {
    public int CountSubMultisets(IList<int> nums, int l, int r) {
        const int MOD = 1000000007;
        var count = new Dictionary<int, int>();
        
        foreach (int num in nums) {
            count[num] = count.GetValueOrDefault(num, 0) + 1;
        }
        
        var dp = new long[r + 1];
        dp[0] = 1;
        
        int zeros = count.GetValueOrDefault(0, 0);
        count.Remove(0);
        
        foreach (var kvp in count) {
            int num = kvp.Key;
            int cnt = kvp.Value;
            
            for (int remainder = 0; remainder < num; remainder++) {
                var vals = new List<long>();
                long sum = 0;
                
                for (int val = remainder; val <= r; val += num) {
                    vals.Add(dp[val]);
                    sum = (sum + dp[val]) % MOD;
                }
                
                for (int i = 0; i < vals.Count; i++) {
                    int val = remainder + i * num;
                    if (i >= cnt + 1) {
                        sum = (sum - vals[i - cnt - 1] + MOD) % MOD;
                    }
                    dp[val] = sum;
                }
            }
        }
        
        long result = 0;
        for (int i = l; i <= r; i++) {
            result = (result + dp[i]) % MOD;
        }
        
        return (int)((result * (zeros + 1)) % MOD);
    }
}

var countSubMultisets = function(nums, l, r) {
    const MOD = 1e9 + 7;
    const count = new Map();
    
    for (const num of nums) {
        count.set(num, (count.get(num) || 0) + 1);
    }
    
    const dp = new Array(r + 1).fill(0);
    dp[0] = 1;
    
    const zeros = count.get(0) || 0;
    count.delete(0);
    
    for (const [num, cnt] of count) {
        for (let remainder = 0; remainder < num; remainder++) {
            const vals = [];
            let sum = 0;
            
            for (let val = remainder; val <= r; val += num) {
                vals.push(dp[val]);
                sum = (sum + dp[val]) % MOD;
            }
            
            for (let i = 0; i < vals.length; i++) {
                const val = remainder + i * num;
                if (i >= cnt + 1) {
                    sum = (sum - vals[i - cnt - 1] + MOD) % MOD;
                }
                dp[val] = sum;
            }
        }
    }
    
    let result = 0;
    for (let i = l; i <= r; i++) {
        result = (result + dp[i]) % MOD;
    }
    
    return (result * (zeros + 1)) % MOD;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(sum × √sum)sum为数组元素和，不同数值个数最多为√sum
空间复杂度O(r)dp数组空间，r为目标范围上界

相关题目