日期：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
