Medium

题目描述

给你一个正整数数组 nums 和一个正整数 k。

你可以对 nums 执行一次操作，在每次操作中，你可以从 nums 中移除任意一个非重叠的前缀和后缀，使得 nums 保持非空。

你需要找到 nums 的 x 值，即执行此操作使得剩余元素的乘积除以 k 的余数为 x 的方法数。

返回一个大小为 k 的数组 result，其中 result[x] 是 nums 在 0 <= x <= k - 1 范围内的 x 值。

数组的前缀是从数组开头开始并延伸到数组内任意点的子数组。

数组的后缀是从数组内任意点开始并延伸到数组末尾的子数组。

注意，操作中选择的前缀和后缀可以为空。

示例 1：

输入：nums = [1,2,3,4,5], k = 3
输出：[9,2,4]

示例 2：

输入：nums = [1,2,4,8,16,32], k = 4
输出：[18,1,2,0]

示例 3：

输入：nums = [1,1,2,1,1], k = 2
输出：[9,6]

约束条件：

  • 1 <= nums[i] <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= k <= 5

解题思路

这道题要求我们计算通过移除前缀和后缀后，剩余元素乘积对k取模的结果为每个可能值的方案数。

核心思路：

  1. 转化问题：移除前缀和后缀等价于选择一个子数组。我们需要统计所有可能的连续子数组，计算它们的乘积对k取模的结果。

  2. 动态规划方法：

    • 定义 dp[i][r] 表示以位置i结尾、乘积模k等于r的子数组个数
    • 对于每个位置i，我们可以：
      • 单独成为一个子数组：dp[i][nums[i] % k] += 1
      • 扩展前面的子数组：dp[i][(prev_r * nums[i]) % k] += dp[i-1][prev_r]

  3. 优化空间：由于k最大为5，我们可以用滚动数组优化空间复杂度。

  4. 统计答案：遍历所有位置，累加每个余数对应的方案数。

时间复杂度：O(n×k)，其中n是数组长度 空间复杂度：O(k)

代码实现

class Solution {
public:
    vector<long long> resultArray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long> result(k, 0);
        
        for (int i = 0; i < n; i++) {
            vector<long long> dp(k, 0);
            dp[nums[i] % k] = 1;
            result[nums[i] % k]++;
            
            for (int j = i - 1; j >= 0; j--) {
                vector<long long> new_dp(k, 0);
                for (int r = 0; r < k; r++) {
                    if (dp[r] > 0) {
                        int new_r = (1LL * r * nums[j]) % k;
                        new_dp[new_r] += dp[r];
                    }
                }
                new_dp[nums[j] % k]++;
                dp = new_dp;
                for (int r = 0; r < k; r++) {
                    result[r] += dp[r];
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def resultArray(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        result = [0] * k
        
        for i in range(n):
            dp = [0] * k
            dp[nums[i] % k] = 1
            result[nums[i] % k] += 1
            
            for j in range(i - 1, -1, -1):
                new_dp = [0] * k
                for r in range(k):
                    if dp[r] > 0:
                        new_r = (r * nums[j]) % k
                        new_dp[new_r] += dp[r]
                new_dp[nums[j] % k] += 1
                dp = new_dp
                for r in range(k):
                    result[r] += dp[r]
        
        return result

public class Solution {
    public long[] ResultArray(int[] nums, int k) {
        int n = nums.Length;
        long[] result = new long[k];
        
        for (int i = 0; i < n; i++) {
            long[] dp = new long[k];
            dp[nums[i] % k] = 1;
            result[nums[i] % k]++;
            
            for (int j = i - 1; j >= 0; j--) {
                long[] newDp = new long[k];
                for (int r = 0; r < k; r++) {
                    if (dp[r] > 0) {
                        int newR = (int)((long)r * nums[j] % k);
                        newDp[newR] += dp[r];
                    }
                }
                newDp[nums[j] % k]++;
                dp = newDp;
                for (int r = 0; r < k; r++) {
                    result[r] += dp[r];
                }
            }
        }
        
        return result;
    }
}

var resultArray = function(nums, k) {
    const n = nums.length;
    const result = new Array(k).fill(0);
    
    for (let i = 0; i < n; i++) {
        let dp = new Array(k).fill(0);
        dp[nums[i] % k] = 1;
        result[nums[i] % k]++;
        
        for (let j = i - 1; j >= 0; j--) {
            const newDp = new Array(k).fill(0);
            for (let r = 0; r < k; r++) {
                if (dp[r] > 0) {
                    const newR = (r * nums[j]) % k;
                    newDp[newR] += dp[r];
                }
            }
            newDp[nums[j] % k]++;
            dp = newDp;
            for (let r = 0; r < k; r++) {
                result[r] += dp[r];
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²×k)双重循环遍历所有子数组，每次需要更新k个状态
空间复杂度O(k)使用长度为k的dp数组存储状态