2026-07-18：可排序整数求和。用go语言，给定一个长度为 n 的整数数组 nums。 现在考虑所有的正整数 k，要求 k 能够整除 n（即 k 是 n 的
🤖 AI总结
主题
算法题解：可排序整数求和
摘要
文章详细讲解了一道算法题：给定整数数组，求所有能通过分段循环平移使数组非递减的因子k之和，并给出了Go、Python、C++代码实现。
关键信息
- 1 给定数组，求所有能使数组通过分段循环平移变成非递减的因子k之和
- 2 预处理nextDec数组记录下降点
- 3 对每个因子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[j+1]的位置j。
• 更准确地说，nextDec[i]存放的是这个“下降位置”的索引。
• 如果从i到末尾都是递增的，则nextDec[i] = n（一个越界标记）。
例如：
• 数组[3, 1, 2]
• 从位置 0 看：3 > 1，所以下降位置是 0，nextDec[0] = 0
• 从位置 1 看：1 < 2，后面没有下降，所以nextDec[1] = 3
• 从位置 2 看：末尾，nextDec[2] = 3
这个预处理很方便我们判断一个子数组[l, r]是不是“至多只有一个下降点”，并确定哪部分是递增的。
第四步：定义检查函数solve(k)
这个函数判断长度为k的段是否可行，并累计可行的k。
我们遍历整个数组，按长度k分块：
1. 对于每个块的起始位置l和结束位置r：
• 取m = nextDec[l]，即从 l 开始的第一个下降位置。
2.情况一：m >= r
• 说明从l到r完全递增。
• 那么这个段本身就有序，不需要平移。
• 它必须满足它的最小值nums[l]≥ 上一段的最大值（因为整体要保持非递减）。
• 如果满足，就更新当前“上一段最大值”为nums[r]。
• 否则，直接返回，k不可行。
3.情况二：m < r
• 说明这段内部存在一个下降，并且根据递减的定义，m是第一个下降位置。
• 这意味着[l, m]这一段是递增的，而[m+1, r]这一段也应该在原始数组中递增（否则会存在第二个下降点，就无法通过一次旋转变成有序）。
• 于是我们需要检查：
•nextDec[m+1] < r表示存在第二个下降点 → 直接失败。
• 第二段的最小值nums[m+1]必须 ≥ 上一段的最大值，否则拼接时会出现下降。
• 第二段的最大值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 = 0，nums[l]=3 ≥ 0 通过，lastMax=3
• 第二块 [1]：1 ≥ 3？不成立，失败。
• 所以 1 不可行。
k = 3
• 一个块 [3,1,2]，l=0，r=2，m=nextDec[0]=0
• 因为 m < r，所以属于情况二：
• nextDec[m+1] = nextDec[1] = 3，等于 r+1，没有第二个下降，通过。
• nums[m+1]=nums[1]=1 ≥ lastMax=0，通过。
• 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完整代码如下：
package main
import (
"fmt"
)
func sortableIntegers(nums []int) (ans int) {
n := len(nums)
nextDec := make([]int, n) // nums[nextDec[i]] > nums[nextDec[i] + 1]
nextDec[n-1] = n
p := n
// 对于每个 i，记录下一个递减的位置
for i := n - 2; i >= 0; i-- {
if nums[i] > nums[i+1] {
p = i
}
nextDec[i] = p
}
solve := func(k int) {
lastMax := 0// 上一段的最大值
for r := k - 1; r < n; r += k {
l := r - k + 1
m := nextDec[l]
if m >= r {
// [l, r] 是递增的，最小值为 nums[l]，最大值为 nums[r]
// 最小值必须 >= 上一段的最大值
if nums[l] < lastMax {
return
}
lastMax = nums[r]
} else {
// [l, m] 是第一段，[m+1, r] 是第二段
// 第二段必须是递增的，且第二段的最小值必须 >= 上一段的最大值，且第二段的最大值必须 <= 第一段的最小值
if nextDec[m+1] < r || nums[m+1] < lastMax || nums[r] > nums[l] {
return
}
lastMax = nums[m]
}
}
ans += k // 满足要求
}
// 枚举 n 的因子 k
for k := 1; k*k <= n; k++ {
if n%k == 0 {
solve(k)
if k*k < n {
solve(n / k)
}
}
}
return
}func main() {
nums := []int{3, 1, 2}
result := sortableIntegers(nums)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
defsortableIntegers(nums):
n = len(nums)
ans = 0
# next_dec[i] 表示从 i 开始第一个递减的位置
# 即 nums[next_dec[i]] > nums[next_dec[i] + 1]
next_dec = [n] * n
p = n
for i inrange(n - 2, -1, -1):
if nums[i] > nums[i + 1]:
p = i
next_dec[i] = p
defsolve(k):
nonlocal ans
last_max = 0# 上一段的最大值
for r inrange(k - 1, n, k):
l = r - k + 1
m = next_dec[l]
if m >= r:
# [l, r] 是递增的，最小值为 nums[l]，最大值为 nums[r]
# 最小值必须 >= 上一段的最大值
if nums[l] < last_max:
return
last_max = nums[r]
else:
# [l, m] 是第一段，[m+1, r] 是第二段
# 第二段必须是递增的，且第二段的最小值必须 >= 上一段的最大值
# 且第二段的最大值必须 <= 第一段的最小值
if next_dec[m + 1] < r or nums[m + 1] < last_max or nums[r] > nums[l]:
return
last_max = nums[m]
ans += k # 满足要求
# 枚举 n 的因子 k
k = 1
while k * k <= n:
if n % k == 0:
solve(k)
if k * k < n:
solve(n // k)
k += 1
return ans# 测试
if __name__ == "__main__":
nums = [3, 1, 2]
result = sortableIntegers(nums)
print(result)
C++完整代码如下：
#include
#include
usingnamespace std;
int sortableIntegers(vector& nums) {
int n = nums.size();
int ans = 0;
// nextDec[i] 表示从 i 开始第一个递减的位置
// 即 nums[nextDec[i]] > nums[nextDec[i] + 1]
vector nextDec(n, n);
int p = n;
for (int i = n - 2; i >= 0; i--) {
if (nums[i] > nums[i + 1]) {
p = i;
}
nextDec[i] = p;
}
// 使用 lambda 表达式定义 solve 函数
auto solve = [&](int k) {
int lastMax = 0; // 上一段的最大值
for (int r = k - 1; r < n; r += k) {
int l = r - k + 1;
int m = nextDec[l];
if (m >= r) {
// [l, r] 是递增的，最小值为 nums[l]，最大值为 nums[r]
// 最小值必须 >= 上一段的最大值
if (nums[l] < lastMax) {
return;
}
lastMax = nums[r];
} else {
// [l, m] 是第一段，[m+1, r] 是第二段
// 第二段必须是递增的，且第二段的最小值必须 >= 上一段的最大值
// 且第二段的最大值必须 <= 第一段的最小值
if (nextDec[m + 1] < r || nums[m + 1] < lastMax || nums[r] > nums[l]) {
return;
}
lastMax = nums[m];
}
}
ans += k; // 满足要求
};
// 枚举 n 的因子 k
for (int k = 1; k * k <= n; k++) {
if (n % k == 0) {
solve(k);
if (k * k < n) {
solve(n / k);
}
}
}
return ans;
}int main() {
vector nums = {3, 1, 2};
int result = sortableIntegers(nums);
cout << result << endl;
return0;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
