LeetCode 解題筆記：3524. Find X Value of Array I

作者：王一哲
日期：2026年9月21日


LeetCode 題目連結：3524. Find X Value of Array I

解題想法

中等難度題，題目正整數陣列 $nums$、一個正整數 $k$，可以移 $nums$ 之中移除不重疊的前綴子陣列及後綴子陣列，使 $nums$ 乘下的元素積乘對 $k$ 取餘數，計算得到各種餘數有幾種方法數。題目下方有提示：

1. 用動態規畫解題。
2. 定義 $dp[i][r]$ 為以索引值 $i$ 為結尾的元素乘積，對 $k$ 取餘數為 $r$ 的方法數。
3. 將每一個索引值的 $dp[i][r]$ 加起來，計算答案 $ans[r]$。

基本上按照提示寫程式碼，應該就可以得到答案。在更新 $dp$ 陣列的過程中，每次相乘後都要對 $k$ 取餘數，可以避免數字過大。而且更新 $dp$ 時只需要用到前一個數字的狀態，可以用滾動陣列節省記憶體。

Python 程式碼

Runtime: 435 ms, beats 26.32%. Memory: 46.36 MB, beats 19.74%.

class Solution:
    def resultArray(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        # dp[i][j] 代表以索引值 i-1 結尾，其元素乘積除以 k 餘數為 j 的子陣列數量
        dp = [[0]*k for _ in range(n+1)]
        ans = [0]*k  # 答案
        for i in range(1, n+1):
            # nums[i-1] 為長度 1 的子陣列
            rem = nums[i-1] % k
            dp[i][rem] = 1
            # 內層迴圈，跑 j = 0 ~ k-1，將目前的數字接在前一個結尾的子陣列之後
            for j in range(k):
                if dp[i-1][j] > 0:  # 如果有前一個結尾對應的子陣列數量
                    new_rem = (j * rem) % k
                    dp[i][new_rem] += dp[i-1][j]
            # 將這一回産生的答案都加到 ans
            for j in range(k):
                ans[j] += dp[i][j]
        # 回傳答案
        return ans

Runtime: 350 ms, beats 76.32%. Memory: 34.22 MB, beats 52.63%.

class Solution:
    def resultArray(self, nums: List[int], k: int) -> List[int]:
        dp = [0]*k  # dp[j] 其元素乘積除以 k 餘數為 j 的子陣列數量
        ans = [0]*k  # 答案
        for num in nums:
            # num 為長度 1 的子陣列
            rem = num % k
            new_dp = [0]*k  # 新的狀態
            new_dp[rem] = 1
            # 內層迴圈，跑 j = 0 ~ k-1，將目前的數字接在前一個結尾的子陣列之後
            for j in range(k):
                if dp[j] > 0:  # 如果有前一個結尾對應的子陣列數量
                    new_rem = (j * rem) % k
                    new_dp[new_rem] += dp[j]
            # 將這一回産生的答案都加到 ans
            for j in range(k):
                ans[j] += new_dp[j]
            # 交換資料
            dp = new_dp
        # 回傳答案
        return ans

C++ 程式碼

Runtime: 147 ms, beats 78.57%. Memory: 173.09 MB, beats 27.68%.

class Solution {
public:
    vector<long long> resultArray(vector<int>& nums, int k) {
        int n = (int)nums.size();
        // dp[i][j] 代表以索引值 i-1 結尾，其元素乘積除以 k 餘數為 j 的子陣列數量
        vector<vector<long long>> dp (n+1, vector<long long> (k, 0LL));
        vector<long long> ans (k, 0LL);  // 答案
        for(int i = 1; i <= n; i++) {
            // nums[i-1] 為長度 1 的子陣列
            long long rem = nums[i-1] % k;
            dp[i][rem] = 1LL;
            // 內層迴圈，跑 j = 0 ~ k-1，將目前的數字接在前一個結尾的子陣列之後
            for(int j = 0; j < k; j++) {
                if (dp[i-1][j] > 0) {  // 如果有前一個結尾對應的子陣列數量
                    long long new_rem = (j * rem) % k;
                    dp[i][new_rem] += dp[i-1][j];
                }
            }
            // 將這一回産生的答案都加到 ans
            for(int j = 0; j < k; j++) {
                ans[j] += dp[i][j];
            }
        }
        return ans;
    }
};

Runtime: 142 ms, beats 81.25%. Memory: 150.99 MB, beats 81.25%.

class Solution {
public:
    vector<long long> resultArray(vector<int>& nums, int k) {
        int n = (int)nums.size();
        vector<long long> dp (k, 0LL);  // dp[j] 代表元素乘積除以 k 餘數為 j 的子陣列數量
        vector<long long> ans (k, 0LL);  // 答案
        for(int num : nums) {
            // num 為長度 1 的子陣列
            long long rem = num % k;
            vector<long long> new_dp (k, 0LL);  // 新的狀態
            new_dp[rem] = 1LL;
            // 內層迴圈，跑 j = 0 ~ k-1，將目前的數字接在前一個結尾的子陣列之後
            for(int j = 0; j < k; j++) {
                if (dp[j] > 0) {  // 如果有前一個結尾對應的子陣列數量
                    long long new_rem = (j * rem) % k;
                    new_dp[new_rem] += dp[j];
                }
            }
            // 將這一回産生的答案都加到 ans
            for(int j = 0; j < k; j++) {
                ans[j] += new_dp[j];
            }
            // 交換資料
            swap(dp, new_dp);
        }
        return ans;
    }
};