2026-07-09：替换最多一个元素后的最长等差子数组。用go语言，给你一个整数数组 nums。 如果某个连续子数组满足：子数组里任意相邻两个元

2026-07-09：替换最多一个元素后的最长等差子数组。用go语言，给你一个整数数组 nums。

如果某个连续子数组满足：子数组里任意相邻两个元素之差都一样（也就是差值恒定），那么这个子数组称为等差子数组。

你最多可以做一次操作：把数组中的任意一个元素替换成任意整数（只允许替换一个位置，且可以选择不替换）。

在完成这次替换（或不替换）后，从数组中挑选一个等差子数组。

要求你返回：在这种条件下，你最多能找到的最长等差子数组的长度。

4 <= nums.length <= 100000。

1 <= nums[i] <= 100000。

输入： nums = [9,7,5,10,1]。

输出： 5。

解释：

将 nums[3] = 10 替换为 3，数组变为 [9, 7, 5, 3, 1]。

选择子数组 [9, 7, 5, 3, 1]，它是等差数组，相邻元素的公差为 -2。

题目来自力扣3872。

一、逐步骤拆解执行流程

数组下标：0:9，1:7，2:5，3:10，4:1

步骤1：初始化基础变量

函数入口：

•n = len(nums) = 5；

•ans = 0，保存全局最优长度；

• 循环变量i从1开始，作为滑动右边界指针。

步骤2：外层循环遍历每一段原生等差区间

循环逻辑：每次取i-1、i作为当前等差段的起始两个点，计算本段公差d，再向右延伸找到本段完整原生等差区间。

第一轮循环初始状态 i=1

1. 标记本段起点start = i-1 = 0；

2. 计算公差d = nums[1]-nums[0] = 7-9 = -2；

3. 向右延伸指针i，不断判断下一对相邻差是否等于d：

• i=2：nums[2]-nums[1]=5-7=-2 == d → i自增到3；

• i=3：nums[3]-nums[2]=10-5=5 ≠ -2 → 停止延伸；
此时确定原生等差区间 [start, i-1] = [0,2]，对应元素[9,7,5]，原生长度3。

步骤3：方案1——尝试修改区间左侧紧邻元素，向左拼接延长

逻辑：修改start-1位置的数字，看能否和当前等差段合并。

1. 判断左边界是否存在：start=0，start >=2不成立，无法向左拼接两段；

2. 左端点最远只能取max(start-1,0)=0；

3. 当前区间右边界是 i-1=2，区间长度 =i - max(start-1,0) = 3-0 =3；

4. 更新ans，当前 ans=3。

步骤4：方案2——尝试修改区间右侧紧邻元素，向右拼接延长

右侧断点是下标 i=3（值10），尝试修改该点，和下一个元素拼接：

1. 判断右侧是否还有元素：i=3 < n-1（4），存在下一位 i+1=4（值1）；

2. 校验拼接条件：nums[i+1] - nums[i-1] == d*2

• nums[i+1]=1，nums[i-1]=5，差值=1-5=-4；

• d=-2，d*2=-4，等式成立；
含义：修改i位置元素后，nums[i-1]、修改后的nums[i]、nums[i+1] 三者公差均为d，能连成等差序列。

3. 继续向右延伸指针j，从i+2=4开始，判断后续相邻差是否等于d：

• j=4：nums[4]-nums[3]=1-10=-9≠-2，循环终止；

4. 可拼接完整区间是[start, j-1] = [0,4]，长度j-start =4-0=5；

5. 更新全局ans，ans从3变为5。

步骤5：判断是否遍历完数组，进入下一段

当前i=3，不等于n=5，外层循环继续，i保持3进入下一轮区间查找。

第二轮外层循环 i=3

1. 本段起点start = i-1 =2；

2. 公差d = nums[3]-nums[2] =10-5=5；

3. 向右延伸i：i自增到4，nums[4]-nums[3]=1-10=-9≠5，停止；
原生等差区间[2,3]，元素[5,10]，原生长度2。

步骤3：修改左侧元素向左拼接

start=2 ≥2，校验nums[start]-nums[start-2] == d*2：

• nums[start]=10，nums[start-2]=9，差值1；

• d*2=10，1≠10，不满足拼接条件；

• 左端点取max(2-1,0)=1，区间长度 i – 1 =4-1=3；
ans当前是5，不更新。

步骤4：修改右侧元素向右拼接

i=4，i < n-1（4<4）不成立；
直接计算区间长度i-start+1 =4-2+1=3，ans仍为5。

步骤5：判断i==n

当前i=4≠5，外层循环继续，i=4进入下一轮区间查找。

第三轮外层循环 i=4

1. start = i-1=3；

2. d = nums[4]-nums[3] =1-10=-9；

3. i自增到5，等于数组长度n，停止向右延伸；
原生等差区间[3,4]，原生长度2。

步骤3：修改左侧元素向左拼接

start=3≥2，校验nums[3]-nums[1] == d*2：
nums[3]=10，nums[1]=7，差值3；d*2=-18，不相等；
左端点取max(3-1,0)=2，区间长度 i -2 =5-2=3，ans不变。

步骤4：修改右侧元素向右拼接

i=5，i < n-1不成立；区间长度5-3+1=3，ans不变。

步骤5：i==n=5，满足返回条件，退出循环，返回ans=5

最终输出结果5，和题目示例匹配。

二、算法通用完整逻辑（脱离示例，通用流程） 阶段1：分割所有天然等差连续段

1. 指针i从1出发，每次取i-1、i作为一段等差区间的起始两点，算出公差d；

2. i持续右移，直到相邻差值不等于d，得到一段完整天然等差区间[start, i-1]；

3. 针对当前这段等差区间，分左右两种修改方案计算最长可拼接长度。

阶段2：左改方案（修改start-1位置元素，向左延长）

目标：只修改1个点，把左边片段和当前等差段合并。

1. 边界判断：若start≥2（左边至少存在两个元素nums[start-2]、nums[start-1]）；

2. 拼接判定条件：nums[start] - nums[start-2] == 2*d

• 原理：修改nums[start-1]后，nums[start-2]、修改后nums[start-1]、nums[start] 公差为d，两段可以无缝拼接；

• 满足条件：合并后区间左边界到start-2，长度i - start + 2；

• 不满足条件：最多只能修改start-1，左边界到start-1，长度i - max(start-1,0)；

3. 用算出的长度更新全局最大值ans。

阶段3：右改方案（修改i位置元素，向右延长）

目标：只修改1个断点i，把当前等差段和右侧元素拼接。

1. 边界判断：i < n-1（右侧还有至少一个元素nums[i+1]）；

2. 拼接判定条件：nums[i+1] - nums[i-1] == 2*d

• 原理：修改nums[i]后，nums[i-1]、修改后nums[i]、nums[i+1] 公差为d；

• 满足条件：继续向右遍历所有后续公差为d的元素，得到最远j，合并区间长度j - start；

• 不满足条件：仅修改i，区间右边界到i，长度i - start + 1；

3. 用算出的长度更新全局最大值ans。

阶段4：循环终止判定

当i右移到数组末尾n时，所有等差段处理完毕，返回全局最大ans。

三、时间复杂度、空间复杂度分析 1. 时间复杂度 O(n)，n为数组长度

• 所有指针i、j均只单向向右移动，全程不会回退；

• 数组每个下标只会被i或j访问1次，不存在嵌套循环重复遍历元素；

• 仅单层线性遍历，所有判断、计算均为常数O(1)操作；

• 数组上限1e5，线性复杂度满足性能要求。

2. 额外空间复杂度 O(1)

• 仅使用固定数量基础变量：n、ans、i、start、d、j；

• 没有开辟数组、哈希表、切片等动态存储，不随输入数组长度变化；

• 仅常数级临时空间。

Go完整代码如下：

package main

 import (
    "fmt"
)

 func longestArithmetic(nums []int) (ans int) {
    n := len(nums)
    for i := 1; ; {
        // 枚举 i-1 和 i 作为等差子数组的前两项，且我们不改 nums[i-1] 和 nums[i]
        start := i - 1
        d := nums[i] - nums[i-1]

         // 往右移动，直到 nums[i] 不满足等差
        for i++; i < n && nums[i]-nums[i-1] == d; i++ {
        }

         // 现在 [start, i-1] 是等差子数组
        // 要想让子数组更长，要么改 nums[start-1]，要么改 nums[i]

         // 改 nums[start-1]
        if start >= 2 && nums[start]-nums[start-2] == d*2 { // 可以和 nums[start-2] 连起来
            ans = max(ans, i-start+2) // 等差子数组 [start-2, i-1]
            // 继续往左延长的情况等同于上一段继续往右延长，无需重复计算
        } else { // 子数组左端点最远只能到 max(start-1,0)
            ans = max(ans, i-max(start-1, 0)) // 等差子数组 [max(start-1,0), i-1]
        }

         if i == n {
            return
        }

         // 改 nums[i]
        if i < n-1 && nums[i+1]-nums[i-1] == d*2 { // 可以和 nums[i+1] 连起来
            // 继续往右延长
            j := i + 2
            for ; j < n && nums[j]-nums[j-1] == d; j++ {
            }
            ans = max(ans, j-start) // 等差子数组 [start, j-1]
        } else { // 子数组右端点最远只能到 i
            ans = max(ans, i-start+1) // 等差子数组 [start, i]
        }
    }
}

 func main() {
    nums := []int{9, 7, 5, 10, 1}
    result := longestArithmetic(nums)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 def longestArithmetic(nums):
    n = len(nums)
    if n < 2:
        return n

     ans = 0
    i = 1
    while True:
        start = i - 1
        d = nums[i] - nums[i - 1]

         # 向右扩展，直到不满足等差
        while i < n and nums[i] - nums[i - 1] == d:
            i += 1

         # 现在 [start, i-1] 是最长等差子数组（不修改任何元素）

         # 尝试修改 nums[start-1] 来延长
        if start >= 2 and nums[start] - nums[start - 2] == d * 2:
            ans = max(ans, i - start + 2)          # 可延长到 start-2
        else:
            ans = max(ans, i - max(start - 1, 0))  # 左端点最多到 max(start-1, 0)

         if i == n:
            return ans

         # 尝试修改 nums[i] 来延长
        if i < n - 1 and nums[i + 1] - nums[i - 1] == d * 2:
            j = i + 2
            while j < n and nums[j] - nums[j - 1] == d:
                j += 1
            ans = max(ans, j - start)              # 可延长到 j-1
        else:
            ans = max(ans, i - start + 1)          # 右端点最多到 i

         # 继续下一轮，i 指向第一个不满足等差的位置

 def main():
    nums = [9, 7, 5, 10, 1]
    result = longestArithmetic(nums)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  

  

  

using namespace std;

 int longestArithmetic(vector& nums) {
    int n = nums.size();
    if (n < 2) return n;

     int ans = 0;
    int i = 1;

     while (true) {
        // 枚举 i-1 和 i 作为等差子数组的前两项，且我们不改 nums[i-1] 和 nums[i]
        int start = i - 1;
        int d = nums[i] - nums[i - 1];

         // 往右移动，直到 nums[i] 不满足等差
        i++;
        while (i < n && nums[i] - nums[i - 1] == d) {
            i++;
        }

         // 现在 [start, i-1] 是等差子数组
        // 要想让子数组更长，要么改 nums[start-1]，要么改 nums[i]

         // 改 nums[start-1]
        if (start >= 2 && nums[start] - nums[start - 2] == d * 2) {
            // 可以和 nums[start-2] 连起来
            ans = max(ans, i - start + 2);  // 等差子数组 [start-2, i-1]
            // 继续往左延长的情况等同于上一段继续往右延长，无需重复计算
        } else {
            // 子数组左端点最远只能到 max(start-1,0)
            ans = max(ans, i - max(start - 1, 0));  // 等差子数组 [max(start-1,0), i-1]
        }

         if (i == n) {
            return ans;
        }

         // 改 nums[i]
        if (i < n - 1 && nums[i + 1] - nums[i - 1] == d * 2) {
            // 可以和 nums[i+1] 连起来
            // 继续往右延长
            int j = i + 2;
            while (j < n && nums[j] - nums[j - 1] == d) {
                j++;
            }
            ans = max(ans, j - start);  // 等差子数组 [start, j-1]
        } else {
            // 子数组右端点最远只能到 i
            ans = max(ans, i - start + 1);  // 等差子数组 [start, i]
        }
    }
}

 int main() {
    vector nums = {9, 7, 5, 10, 1};
    int result = longestArithmetic(nums);
    cout << result << endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。