2026-07-18：可排序整数求和。用go语言，给定一个长度为 n 的整数数组 nums。 现在考虑所有的正整数 k，要求 k 能够整除 n（即 k 是 n 的因数）。 对于这样的每个 k，我们把数

2026-07-18可排序整数求和。用go语言给定一个长度为 n 的整数数组 nums。现在考虑所有的正整数 k要求 k 能够整除 n即 k 是 n 的因数。对于这样的每个 k我们把数组按顺序分成若干个长度都为 k 的小段最后一段不会多余因为 k 整除 n。然后允许我们对每一小段内部独立地做任意次数的循环平移可以向左或向右旋转任意步数。如果经过这样处理之后整个数组能够变成非递减的顺序从小到大排列那么就称 k 是一个“可排序整数”。最后请你找出所有满足条件的 k并把它们相加返回这个总和。1 n nums.length 100000。1 nums[i] 100000。输入 nums [3,1,2]。输出 3。解释​​​​​​​对于 n 3可能的因数是 1 和 3。对于 k 1每个子数组都只有一个元素。无法通过移动使数组排序。对于 k 3单个子数组 [3, 1, 2] 可以通过左移一次得到 [1, 2, 3]从而将数组排序。只有 k 3 可排序因此答案是 3。题目来自力扣3886。第一步理解题目要求我们有一个数组nums长度n。只考虑那些能整除n的正整数k即n % k 0。将数组切成连续的、长度都为k的小段。每一段内部可以任意次数地循环平移左移或右移任意步数。如果经过这些段内平移之后整个数组能够变成全局非递减的升序允许相等那么这个k就是“可排序整数”。最后把全部“可排序整数”加起来返回总和。第二步对于给定的k判断其是否可行的核心思路要判断一个k是否可行我们可以一段一段地检查。每个段内部的元素可以通过循环平移得到任意循环排列因此我们需要知道每一段经过平移后能形成的最小值和最大值以及它们之间的相对顺序限制。比如如果一段内部本来就是非递减的那么它不用平移就符合要求不过可以平移但没必要。如果一段内部不是单调递增的那么它的唯一可能的平移后有序情况是该段必须恰好由一个下降点分成两个递增区间然后将这两个区间交换顺序相当于旋转一次才能成为升序。因此我们需要提前知道每个位置“下一个递减开始的位置”。第三步预处理 —— 记录“下一个递减位置”代码中有一个数组nextDec长度为n。nextDec[i]表示从索引i开始往后第一个满足nums[j] nums[j1]的位置j。更准确地说nextDec[i]存放的是这个“下降位置”的索引。如果从i到末尾都是递增的则nextDec[i] n一个越界标记。例如数组[3, 1, 2]从位置 0 看3 1所以下降位置是 0nextDec[0] 0从位置 1 看1 2后面没有下降所以nextDec[1] 3从位置 2 看末尾nextDec[2] 3这个预处理很方便我们判断一个子数组[l, r]是不是“至多只有一个下降点”并确定哪部分是递增的。第四步定义检查函数solve(k)这个函数判断长度为k的段是否可行并累计可行的k。我们遍历整个数组按长度k分块对于每个块的起始位置l和结束位置r取m nextDec[l]即从 l 开始的第一个下降位置。情况一m r说明从l到r完全递增。那么这个段本身就有序不需要平移。它必须满足它的最小值nums[l]≥ 上一段的最大值因为整体要保持非递减。如果满足就更新当前“上一段最大值”为nums[r]。否则直接返回k不可行。情况二m r说明这段内部存在一个下降并且根据递减的定义m是第一个下降位置。这意味着[l, m]这一段是递增的而[m1, r]这一段也应该在原始数组中递增否则会存在第二个下降点就无法通过一次旋转变成有序。于是我们需要检查nextDec[m1] r表示存在第二个下降点 → 直接失败。第二段的最小值nums[m1]必须 ≥ 上一段的最大值否则拼接时会出现下降。第二段的最大值nums[r]必须 ≤ 第一段的最小值nums[l]因为平移后我们通常把第二段放到前面相当于旋转。如果满足这些条件那么平移后可以有序更新上一段最大值为第一段的最大值nums[m]因为平移后第一段在后面。当所有段都通过检查则k可行累加到答案中。第五步枚举所有因子 k因为k必须是n的因子我们可以只枚举因子不用遍历 1…n。做法从k 1到sqrt(n)检查n % k 0检查k如果k*k ! n再检查n/k这样就能遍历所有正因子。第六步返回总和所有可行的k累加到ans最后返回。例子nums [3, 1, 2]n 3因子有 1, 3预处理nextDec[0, 3, 3]k 1每个块长度 1第一块 [3]上一段最大值 lastMax 0nums[l]3 ≥ 0 通过lastMax3第二块 [1]1 ≥ 3不成立失败。所以 1 不可行。k 3一个块 [3,1,2]l0r2mnextDec[0]0因为 m r所以属于情况二nextDec[m1] nextDec[1] 3等于 r1没有第二个下降通过。nums[m1]nums[1]1 ≥ lastMax0通过。nums[r]nums[2]2 ≤ nums[l]3通过。更新 lastMax nums[m] nums[0] 3。没有更多段成功。所以 3 可行。答案 3。时间和空间复杂度分析时间复杂度预处理nextDec需要 O(n)。枚举因子数量是 O(√n)。每个因子检查时会遍历数组一遍即 O(n)。总复杂度为 O(n * d(n))其中 d(n) 是因子个数。因子个数最大在 n ≤ 1e5 时很少通常几十个可以认为是 O(n √n) 的宽松上界但实际因子数很小可以认为是 O(n * τ(n))在本题限制下可行。额外空间复杂度只用了nextDec数组长度 n因此额外空间为 O(n)。Go完整代码如下packagemainimport(fmt)funcsortableIntegers(nums[]int)(ansint){n:len(nums)nextDec:make([]int,n)// nums[nextDec[i]] nums[nextDec[i] 1]nextDec[n-1]n p:n// 对于每个 i记录下一个递减的位置fori:n-2;i0;i--{ifnums[i]nums[i1]{pi}nextDec[i]p}solve:func(kint){lastMax:0// 上一段的最大值forr:k-1;rn;rk{l:r-k1m:nextDec[l]ifmr{// [l, r] 是递增的最小值为 nums[l]最大值为 nums[r]// 最小值必须 上一段的最大值ifnums[l]lastMax{return}lastMaxnums[r]}else{// [l, m] 是第一段[m1, r] 是第二段// 第二段必须是递增的且第二段的最小值必须 上一段的最大值且第二段的最大值必须 第一段的最小值ifnextDec[m1]r||nums[m1]lastMax||nums[r]nums[l]{return}lastMaxnums[m]}}ansk// 满足要求}// 枚举 n 的因子 kfork:1;k*kn;k{ifn%k0{solve(k)ifk*kn{solve(n/k)}}}return}funcmain(){nums:[]int{3,1,2}result:sortableIntegers(nums)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defsortableIntegers(nums):nlen(nums)ans0# next_dec[i] 表示从 i 开始第一个递减的位置# 即 nums[next_dec[i]] nums[next_dec[i] 1]next_dec[n]*n pnforiinrange(n-2,-1,-1):ifnums[i]nums[i1]:pi next_dec[i]pdefsolve(k):nonlocalans last_max0# 上一段的最大值forrinrange(k-1,n,k):lr-k1mnext_dec[l]ifmr:# [l, r] 是递增的最小值为 nums[l]最大值为 nums[r]# 最小值必须 上一段的最大值ifnums[l]last_max:returnlast_maxnums[r]else:# [l, m] 是第一段[m1, r] 是第二段# 第二段必须是递增的且第二段的最小值必须 上一段的最大值# 且第二段的最大值必须 第一段的最小值ifnext_dec[m1]rornums[m1]last_maxornums[r]nums[l]:returnlast_maxnums[m]ansk# 满足要求# 枚举 n 的因子 kk1whilek*kn:ifn%k0:solve(k)ifk*kn:solve(n//k)k1returnans# 测试if__name____main__:nums[3,1,2]resultsortableIntegers(nums)print(result)C完整代码如下#includeiostream#includevectorusingnamespacestd;intsortableIntegers(vectorintnums){intnnums.size();intans0;// nextDec[i] 表示从 i 开始第一个递减的位置// 即 nums[nextDec[i]] nums[nextDec[i] 1]vectorintnextDec(n,n);intpn;for(intin-2;i0;i--){if(nums[i]nums[i1]){pi;}nextDec[i]p;}// 使用 lambda 表达式定义 solve 函数autosolve[](intk){intlastMax0;// 上一段的最大值for(intrk-1;rn;rk){intlr-k1;intmnextDec[l];if(mr){// [l, r] 是递增的最小值为 nums[l]最大值为 nums[r]// 最小值必须 上一段的最大值if(nums[l]lastMax){return;}lastMaxnums[r];}else{// [l, m] 是第一段[m1, r] 是第二段// 第二段必须是递增的且第二段的最小值必须 上一段的最大值// 且第二段的最大值必须 第一段的最小值if(nextDec[m1]r||nums[m1]lastMax||nums[r]nums[l]){return;}lastMaxnums[m];}}ansk;// 满足要求};// 枚举 n 的因子 kfor(intk1;k*kn;k){if(n%k0){solve(k);if(k*kn){solve(n/k);}}}returnans;}intmain(){vectorintnums{3,1,2};intresultsortableIntegers(nums);coutresultendl;return0;}