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

福大大架构师每日一题

发布于 2026-07-21 13:27:29

780

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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 <iostream>
#include <vector>
usingnamespace std;

int sortableIntegers(vector<int>& nums) {
    int n = nums.size();
    int ans = 0;

    // nextDec[i] 表示从 i 开始第一个递减的位置
    // 即 nums[nextDec[i]] > nums[nextDec[i] + 1]
    vector<int> 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<int> nums = {3, 1, 2};
    int result = sortableIntegers(nums);
    cout << result << endl;
    return0;
}