LeetCode 解題筆記：3886. Sum of Sortable Integers

作者：王一哲
日期：2026年10月20日


LeetCode 題目連結：3886. Sum of Sortable Integers

解題想法

困難題。題目給一個長度為 $n ~(1 \leq n \leq 10^5)$ 的整數陣列 $nums ~(1 \leq nums[i] \leq 10^5)$，如果將 $nums$ 切成長度為 $k$ 的子陣列，如果可以將子陣列以滾動的方式使得 $nums$ 由小到大排序，求所有符合條件的 $k$ 值加總。

這題下方有提示，基本上就是按照題示寫程式碼。寫一個檢驗 $k$ 是否符合條件的自訂函式 $check$，定義前一個子陣列的最小值 prev_max，預設為小於題目測資範圍的 $-100000000$。用一個 for 迴圈檢查分割 $nums$ 為長度為 $k$ 的子陣列，定義子陣列最小值 sub_min、最大值 sub_max，兩者皆預設為$nums[i]$，子陣列遞減次數 $drop$ 預設為 $0$。裡面再用一個 for 迴圈，檢查長度為 $k$ 的區間內部。如果子陣列可以用滾動的方式由小到大排列，則子陣列中遞減的次數最多只有 1 次；如果遞減次數為 1 次，則子陣列的首項必須大於、等於末項；這個子陣列的最小值必須大於、等於前一個子陣列的最大值。

由於題目要將 $nums$ 分割為長度均為 $k$ 的子陣列，因此 $k$ 一定是 $n$ 的因數，再加上 $n$ 的最大值為 $100000$，要測試的因數 $k$ 最大為 $\sqrt{n} \approx 316$，如果在這個範圍內找到因數 $k$，同時再檢查對應的因數 $p = n / k$，需要檢查的次數並不多，可以用 for 迴圈暴力解。

Python 程式碼

Runtime: 2965 ms, beats 29.67%. Memory: 31.36 MB, beats 69.23%.

class Solution:
    def sortableIntegers(self, nums: list[int]) -> int:
        n = len(nums)

        # 1. 自訂函式，檢驗 nums 切成長度 k 的子陣列是否能排序
        def check(k):
            prev_max = -float('inf')  # 前一個子陣列的最小值
            for i in range(0, n, k):  # 分割 nums 為長度 k 的子陣列
                sub_min = sub_max = nums[i]  # 子陣列最小值、最大值，預設為 nums[i]
                drop = 0  # 遞減次數
                # 檢查長度 k 的區間內部
                for j in range(i, i + k - 1):
                    if nums[j] > nums[j + 1]:  # 遞減
                        drop += 1
                    # 更新 sub_min, sub_max
                    if nums[j + 1] < sub_min:
                        sub_min = nums[j + 1] 
                    elif nums[j + 1] > sub_max:
                        sub_max = nums[j + 1]
                
                # 條件1，如果遞減次數大於1，無法排序
                if drop > 1: return False
                # 條件2，如果遞減1次，子陣列末項必須小於、等於首項
                if drop == 1 and nums[i + k - 1] > nums[i]:
                    return False
                # 條件3，這一區最小值大於、等於前一區最大值
                if sub_min < prev_max: return False

                # 更新 prev_max
                prev_max = sub_max
            
            # 通過測試，回傳 True
            return True
        
        # 2. 找出 n 的所有因數 k，呼叫 check 測試因數 k
        ans = 0  # 答案
        for k in range(1, int(n**0.5) + 1):
            if n % k == 0:
                # 驗證因數 k
                if check(k): ans += k
                # 驗證對稱的因數 n // k，且 k != n // k
                if k != n // k:
                    if check(n // k): ans += n // k
        return ans

C++ 程式碼

Runtime: 42 ms, beats 89.71%. Memory: 88.26 MB, beats 96.32%.

class Solution {
public:
    // 自訂函式 check，檢驗將 nums 切成長度 k 的子陣列是否可排序
    bool check(int k, const vector<int>& nums) {
        // 長度，前一個子陣列的最大值
        int n = (int)nums.size(), prev_max = -1000000000;
        // 檢查各個長度為 k 的子陣列
        for(int i = 0; i < n; i += k) {
            // 遞減次數，子陣列的最大值、最小值，預設為 nums[j]
            int drop = 0, sub_max = nums[i], sub_min = nums[i];
            for(int j = i; j < i + k - 1; j++) {
                // 遞減
                if (nums[j + 1] < nums[j]) {
                    drop++;
                }
                // 更新子陣列最大值、最小值
                if (nums[j + 1] > sub_max) {
                    sub_max = nums[j + 1];
                } else if (nums[j + 1] < sub_min) {
                    sub_min = nums[j + 1];
                }
            }
            // 條件1，遞減次數不能大於 1
            if (drop > 1) return false;
            // 條件2，遞減次數1次，子陣列首項必須大於、等於末項
            if (drop == 1 && nums[i] < nums[i + k - 1]) return false;
            // 條件3，子陣列最小值必須大於、等於前一個子陣列的最大值
            if (sub_min < prev_max) return false;
            // 更新 prev_max
            prev_max = sub_max;
        }
        return true;  // 通過測試，回傳 true
    }

    int sortableIntegers(vector<int>& nums) {
        // 測試 nums 長度 n 所有的因數
        int n = (int)nums.size(), ans = 0;
        for(int k = 1; k <= (int)sqrt(n); k++) {
            if (n % k == 0) {
                if (check(k, nums)) ans += k;
                int p = n / k;  // 對應的因數
                if (k != p) {  // 避免相等的值
                    if (check(p, nums)) ans += p;
                }
            }
        }
        return ans;
    }
};

C 語言程式碼

Runtime: 84 ms, beats 69.57%. Memory: 16.58 MB, beats 100.00%.

// 自訂函式 check，檢驗將 nums 切成長度 k 的子陣列是否可排序
int check(int k, int* nums, int numsSize) {
    // 前一個子陣列的最大值
    int prev_max = -1000000000;
    // 檢查各個長度為 k 的子陣列
    for(int i = 0; i < numsSize; i += k) {
        // 遞減次數，子陣列的最大值、最小值，預設為 nums[j]
        int drop = 0, sub_max = nums[i], sub_min = nums[i];
        for(int j = i; j < i + k - 1; j++) {
            // 遞減
            if (nums[j + 1] < nums[j]) {
                drop++;
            }
            // 更新子陣列最大值、最小值
            if (nums[j + 1] > sub_max) {
                sub_max = nums[j + 1];
            } else if (nums[j + 1] < sub_min) {
                sub_min = nums[j + 1];
            }
        }
        // 條件1，遞減次數不能大於 1
        if (drop > 1) return 0;
        // 條件2，遞減次數1次，子陣列首項必須大於、等於末項
        if (drop == 1 && nums[i] < nums[i + k - 1]) return 0;
        // 條件3，子陣列最小值必須大於、等於前一個子陣列的最大值
        if (sub_min < prev_max) return 0;
        // 更新 prev_max
        prev_max = sub_max;
    }
    return 1;  // 通過測試，回傳 1
}

int sortableIntegers(int* nums, int numsSize) {
    // 測試 nums 長度 n 所有的因數
    int ans = 0;
    for(int k = 1; k <= (int)sqrt(numsSize); k++) {
        if (numsSize % k == 0) {
            if (check(k, nums, numsSize)) ans += k;
            int p = numsSize / k;  // 對應的因數
            if (k != p) {  // 避免相等的值
                if (check(p, nums, numsSize)) ans += p;
            }
        }
    }
    return ans;
}