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

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是否可行，我们可以一段一段地检查。

每个段内部的元素可以通过循环平移得到任意循环排列，因此我们需要知道每一段经过平移后能形成的最小值和最大值，以及它们之间的相对顺序限制。

比如：

• • 如果一段内部本来就是非递减的，那么它不用平移就符合要求（不过可以平移，但没必要）。

• • 如果一段内部不是单调递增的，那么它的唯一可能的平移后有序情况是：该段必须恰好由一个下降点分成两个递增区间，然后将这两个区间交换顺序（相当于旋转一次），才能成为升序。

因此，我们需要提前知道每个位置“下一个递减开始的位置”。

第三步：预处理 —— 记录“下一个递减位置”

代码中有一个数组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. 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)。

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助力您的未来发展。