1. 问题拆解与思路选择1.1 先说清楚这道题到底在考什么“问题 N: 等差数”这个标题本身很简单但恰恰是这种极简的题目名放在任何一场竞赛、考试或算法练习里都可能对应着三种截然不同的问法给定首项、公差、项数让你输出等差数列的某一项或前 N 项之和给定一个数列判断它是不是等差数列在一个区间或序列中统计满足等差性质的子序列/子数组数量。我在实际带项目、做算法题解时见过太多次这种“极简标题陷阱”很多人一看到“等差数”三个字条件反射就去套a_n a_1 (n-1)*d这个公式结果题目真正考察的是后面两种——判断和计数。所以我每次拿到这种题目第一件事永远是先把题目原文完整读三遍搞清楚输入输出和边界条件再去动笔写公式。这篇文章不针对某一场具体比赛的某个版本而是把“等差数”这类问题背后的通用套路拆开讲透覆盖从 O(1) 公式计算到 O(n^2) 区间枚举的常见解法。无论你遇到的是哪种变体都能在这篇文章里找到对应的思考路径。1.2 为什么这类题目容易“翻车”等差数列是中学数学就讲过的基础概念按理说难度不高但实际做题时翻车率却很高。我总结下来主要有三个原因第一很多人忽略整数溢出问题。题目通常不会给你温馨提醒“答案可能超过 int 范围”但实际数据里首项 10^9、公差 10^9、项数 10^5 的组合非常常见前 N 项和用 int 存直接就溢出了。我见过太多人在这一步吃亏。第二判断等差时只检查相邻两项差值忽略了空序列、单元素序列、重复元素序列等边界。空集和单元素集在数学定义上算不算等差数列不同题目约定不同但很多人压根没意识到要去读题面里关于这个的定义。第三计数类变体特别容易写出 O(n^3) 的暴力代码样例能过一提交就超时。这类题表面上是“等差数”实际上考察的是枚举技巧和哈希表优化。2. 核心概念与基础知识补充2.1 等差数列的三种等价判定方式在动手写代码之前有几个基础知识点值得先明确。判断一个序列是否为等差数列可以用三种等价的视角第一种是递推视角对于连续三项a, b, c满足b - a c - b即2*b a c。这个形式在很多题目里更实用因为避免了一次减法某些语言里可以减少大整数运算的精度问题。第二种是通项视角如果已知首项a_1和公差d那么第 n 项就是a_n a_1 (n-1)*d。这个用于直接求某一项非常快时间复杂度是 O(1)。第三种是求和视角前 n 项和等于n * (a_1 a_n) / 2或者n * a_1 n*(n-1)*d/2。这个公式不仅用于求值还经常反过来用——给你一个和让你反推是否存在某个等差数列满足条件这类题在数论和构造题里非常常见。这三种视角没有优劣之分关键是看题目给的已知条件是什么。如果已知首项和公差就用通项公式如果已知前几项需要判断等差就用递推视角如果已知总和需要反推就用求和公式配合整除判断。2.2 常见变体的识别方法我把“等差数”相关的题目粗略分成四类每一类的解题策略完全不同类型典型问法核心方法时间复杂度求项/求和求第 n 项、前 n 项和公式直接计算O(1)判断判断给定序列是否为等差遍历相邻差O(n)构造给定若干条件构造等差序列数学推导枚举O(n) 或 O(n^2)计数统计等差子序列/子数组数量动态规划/哈希表O(n^2)拿到题目后先分类再决定用什么思路。这听起来像废话但我见过很多人在“求项”的题里非要写个循环迭代或者在“判断”的题里先去排序——排序会把原有顺序破坏掉判断结果自然是错的这就是典型的思路没有先跟上。3. 基础实现求第 n 项与前 n 项和3.1 直接套公式的写法如果你遇到的“等差数”题目是最基础的版本——给定首项a1、公差d和项数n让求第n项或前n项和那么直接用公式就行没什么好犹豫的。下面给出一个同时支持两种查询的示例代码def arithmetic_sequence(a1: int, d: int, n: int): # 第 n 项 an a1 (n - 1) * d # 前 n 项和 sn n * (a1 an) // 2 return an, sn print(arithmetic_sequence(2, 3, 5)) # 第5项14前5项和40这段代码看起来简单但有几个细节值得展开讲。第一个细节是// 2的除法时机。前 n 项和公式n * (a1 an) / 2里的除法推荐全部乘完再做整除而不是边乘边除。原因有两个一是避免浮点数精度问题二是保证结果是整数。很多语言里如果写成(n / 2) * (a1 an)当n是奇数时先除会得到小数后续乘以整数结果可能就出现了精度偏差。第二个细节是数据类型的长度。Python 的 int 是无限精度的写这段代码不会遇到溢出问题。但如果你用的是 C 或 Java就必须小心中间结果n * (a1 an)可能远超最终答案的范围。比如a110^9, d10^9, n10^5时an是10^14级别n * (a1 an)是10^19级别已经超出 64 位有符号整数的最大值约9.2 * 10^18。稳妥的做法是用__int128C或BigIntegerJava或者先用公式变形减少中间量。第三个细节是公差的符号。等差数列的公差不一定是正的可以是负数、零甚至题目可能故意给一个递减序列。a1 10, d -2, n 4时第 4 项是4前 4 项和是28这些情况代码都能正确处理但如果你在公式里写成了a1 (n 1) * d或者n * (a1 an) / 2 1这种“微调”版本就会在负数公差上出问题。所以公式本身不要乱改符号全部由参数决定。3.2 边界条件与隐藏坑位基础题目虽然直接套公式但边界条件仍然值得单独拿出来说。n 0的情况。数学上空序列的前 0 项和定义为 0但第 0 项是什么有的题目约定第 0 项就是首项有的题目不允许查询第 0 项。我建议代码逻辑上做一层防御如果n 0返回 0 或抛出异常不参与公式计算。这种防御不仅让代码更健壮也能防止在实际工程中被上游调用的脏数据打崩。d 0的情况。所有人看到这个第一反应是“全部相等仍然是等差数列”这个没错。但注意如果题目要求“严格等差”即相邻两项差值必须非零那么d 0会被排除在外。考试和面试里经常在这个点上设陷阱。你需要看题目里有没有出现“严格”两个字。a1 an的奇偶性问题。我们使用整除公式时有一个隐含前提n * (a1 an)必须是偶数。这其实自动成立因为等差数列前 n 项和一定是整数。但在构造类题目中如果你手算推导出一个类似x n*(ab)//2的公式而这个公式本身并不保证整除那么就需要用if判断一下能否整除否则不能直接用这个公式构造。注意我在实际做题和写工程代码时有一个习惯——写完公式后用最简单的用例验证一遍a11, d1, n5结果应该是第 5 项等于 5前 5 项和等于 15。这个用例花不了一秒钟但能拦住 90% 的低级笔误。4. 判断一个序列是否为等差数列4.1 常规判断与陷阱再来说第二种常见版本给你一个长度为 n 的数组判断它是否构成等差数列。最直接的办法是先把数组长度n和元素取出如果n 2直接返回 True——因为任意两个数都可以看作是等差数列或者按题面约定空/单元素也成立。然后遍历一次计算arr[1] - arr[0]作为公差d再逐个检查arr[i] - arr[i-1]是否等于d。def is_arithmetic(arr): n len(arr) if n 2: return True d arr[1] - arr[0] for i in range(2, n): if arr[i] - arr[i-1] ! d: return False return True这段代码时间复杂度 O(n)是标准解法。但我要提一个非常容易被忽视的点不能先排序再判断。我遇到过不止一次有同学把数组先sort()一下然后判断相邻差值是否相等。排序会改变元素的原始顺序而等差数列对顺序非常敏感。比如[2, 4, 6, 3, 5]排序后是[2, 3, 4, 5, 6]相邻差值都是 1判断结果是 True但原始序列[2, 4, 6, 3, 5]并不是等差。所以这个坑一定不要踩。如果题目要求判断“无序数组能否重排成等差数列”那才需要排序这是另一回事。判断的关键词是“重排”还是“原来的顺序”。这两个词差了十万八千里。4.2 更快的判断思路在工程场景中有时会遇到超大规模数组比如上亿条的时序数据你想快速知道是否存在某个连续子段是等差的。这时候 O(n) 的遍历虽然已经是线性但配合滑动窗口和剪枝还能进一步提速。一个常见的优化思路是如果数组的长度很长而题目允许只判断整个数组是否为等差那么可以先用开头两个元素求公差然后再扫描。这里不存在理论上的更快算法——因为判断本身需要读一遍所有元素O(n) 已经是最优。但在特定场景下可以用“抽样预检”做启发式优化先检查arr[0], arr[1], arr[2]是否等差再检查arr[0], arr[1], arr[n//2]是否满足通项公式。如果抽样不满足就可以提前结束避免全量扫描。这个技巧在面试的 System Design 讨论里反而经常出现——它并不是理论最优但在大数据量下能显著减少平均扫描时间。我个人的建议是如果是在竞赛或刷题场景老老实实全量遍历即可不要炫技如果是处理真实的海量数据抽样预检值得一试。两者目标不同优化思路也要跟着调整。5. 进阶变体等差子序列的计数5.1 暴力枚举的问题“等差数”题目中最棘手也最常考的变体是“给定一个数组统计其中等差子序列或等差子数组的个数”。先说子数组版本。子数组要求连续暴力思路是枚举所有起点i和终点j然后判断arr[i:j1]是否等差时间复杂度 O(n^3)。n100时勉强能跑n1000就开始卡n10^4以上必然超时。优化到 O(n^2) 的思路很清晰固定起点i逐步扩展终点j同时维护当前的公差。当加入新元素arr[j]时只要arr[j] - arr[j-1]仍然等于当前公差那么这个子数组就是等差的计数加一一旦不等于就 break因为再往后也不可能恢复连续等差。def count_arithmetic_subarrays(arr): n len(arr) count 0 for i in range(n): if i 2 n: break d arr[i1] - arr[i] count 1 # 长度为2的子数组也计入的话 for j in range(i2, n): if arr[j] - arr[j-1] d: count 1 else: break return count这段代码用了“只考虑长度至少为 2 的子数组”的约定。实际题目里单元素子数组是否计入需要看题面不同题目约定不同。我个人写代码时习惯把“长度 1 的子数组”作为特殊情况在开头单独讨论不要混进主逻辑容易乱。5.2 不连续子序列的计数动态规划与哈希表如果是统计不连续的子序列元素不一定相邻但相对顺序不变问题难度就上一个台阶。此时[1, 2, 3, 4]中的[1, 3]也可以构成等差子序列公差 2[1, 2, 3]是等差[1, 2, 4]不是。经典的解法是动态规划 哈希表。定义dp[i][d]表示以位置i结尾、公差为d的等差子序列数量。对于固定的i遍历所有j i计算出d arr[i] - arr[j]然后dp[i][d] dp[j][d] 1其中1表示新形成的长度为 2 的子序列[j, i]最终答案累加所有dp[i][d]同时可以根据需要减去长度为 2 的序列数量。这个解法的时间复杂度是 O(n^2)空间复杂度也是 O(n^2)哈希表的键数量可能有 O(n^2) 种。但对于数据规模中等比如n 2000的题目完全够用。def count_arithmetic_subsequences(arr): n len(arr) from collections import defaultdict dp [defaultdict(int) for _ in range(n)] total 0 for i in range(n): for j in range(i): d arr[i] - arr[j] dp[i][d] dp[j][d] 1 total dp[i][d] # total 包含所有长度2的子序列 return total这里有个容易出现的小偏差total把所有长度为 2 的序列也计入了而长度为 2 的任意两个元素都可以视为等差数列所以如果你最后想统计的是“长度至少为 3”的子序列需要在累加时减去n*(n-1)//2或者只在dp[j][d] 0时才把当前的dp[i][d]加入答案。两种做法都对但一定要保持一致不要混着用。5.3 为什么不用二维数组代替哈希表有人会问公差d的范围如果不大直接用二维数组dp[n][范围]是不是更快理论上如果d的范围有限且可预估用数组确实比哈希表快。但实际题目的数据范围经常把公差范围拉得很大比如arr[i]在[-10^9, 10^9]之间公差范围就有2*10^9 1种可能二维数组根本开不下。这时候必须用哈希表让键只存储实际出现的公差。另外用哈希表存公差还有一个隐藏好处负数公差和零公差都可以作为键直接存储不需要做下标偏移。如果你非要用数组还得额外写一个d offset的映射逻辑一旦忘了处理负数程序就会越界崩溃。这也是我不建议用数组的原因。6. 构造类变体给定条件反推等差数列6.1 常见构造思路另一种“等差数”题目偏向数学构造。典型的问法包括给定首项和末项以及项数 n是否存在一组合法的整数公差给定若干项的约束例如第 2 项和第 5 项的值能否唯一确定整个等差序列将一个整数 n 拆成若干项等差数之和问有哪些拆法。这类题的核心是反推公差。比如给定首项a1、末项an和项数n求解公差的公式是d (an - a1) / (n - 1)判断是否有整数解的条件是(an - a1) % (n - 1) 0。这个取模判断非常关键因为题目通常要求每一项都是整数。不能整除时直接返回“不存在合法序列”。def try_construct(a1, an, n): if n 0: return None if n 1: return [] if a1 an else None if (an - a1) % (n - 1) ! 0: return None d (an - a1) // (n - 1) return [a1 i * d for i in range(n)]这个代码的逻辑很直接但我要强调一个隐含的边界如果n 1那么n - 1 0做除法会直接报错或返回无穷大。所以必须先特判。我见过不少人在 LeetCode 风格的题目里踩这个雷导致边界用例直接 Runtime Error。6.2 多条件下的公差不唯一问题还有一种更复杂的构造场景题目只告诉你“某几项的值”但没告诉你它们分别对应第几项而是给你一个无序的多重集合让你判断能否把这些数排成一个等差数列。这个问题的经典解法是先排序然后用首尾元素推导公差。但也有例外——如果集合里有重复元素排序后首尾元素可能无法唯一确定公差。比如集合[2, 2, 2, 4]排完序后首项 2、末项 4、长度 4公差算出来是(4-2)/(4-1)不是整数按公式判断不存在。但实际上[2, 2, 2, 4]明显不是等差前面三个相同最后突变。所以这里的“按公式计算”仍然有效因为它要求的是整个集合能构成一个等差数列而不仅仅是首尾匹配。但假如集合是[1, 3, 5, 7]显然可以组成公差 2 的等差。此时首尾公式给出的公差是(7-1)/(4-1)2与直觉一致。真正棘手的情况是集合中存在重复元素且长度较大时你可能会被“公差是否是整数”这个条件骗到。例如集合[1, 1, 2, 2]排序后首 1 末 2长度 4(2-1)/(4-1)不是整数所以判断“不可构成等差”——这个结论是正确的。但如果你在代码里把公差算成了浮点数0.333...再拿它去检查其他元素是否匹配就会出现浮点数精度问题可能在特殊用例上报错。因此我总是建议用整数运算加取模判断尽量避开浮点数。7. 常见错误与排查技巧实录7.1 从我自己的踩坑经历说起我第一次在竞赛里被“等差数”题目坑到是一道看似简单的判断题。当时题目给了一个大数组我写完is_arithmetic函数之后本地测试全过一提交就错。反复看了很久才发现问题出在输入格式上——题目里的数组元素是在同一行以空格分隔给出的我用的语言默认按换行读取导致第一个元素读成了整行字符串后续全错。从那之后我养成一个习惯拿到任何输入输出题目先写一个极小的输入样例手动跑一遍输出确信读入逻辑没问题后再写核心算法。这个习惯帮我省下了很多无意义的调试时间。另一个高频错误是忘记考虑n 2的特殊情况。本质上其实是“对题目的边界条件定义不敏感”。比如 LeetCode 上很多题把长度为 0 或 1 的数组视为等差但有些数学定义里空集不一定算。这没有统一标准必须以题面为准。如果题面没说我的默认策略是“保守处理”——把长度小于等于 2 的序列当作等差返回 True但在代码注释里明确标记方便后续产品逻辑修改时快速定位。7.2 典型问题速查表症状可能原因排查方向求和结果比预期大很多中间乘法溢出检查是否使用了足够宽的数据类型结果有小数/浮点误差除法用了浮点改用整数除法并先判断整除判断结果错误先排序丢了原顺序去掉 sort保持原数组顺序计数结果偏多/偏少长度为 2 的子序列是否计入没统一明确约定并保持计算一致边界用例崩溃n0 或 n1 时除零提前特判长度公差为负数时结果错误公式或逻辑中假设了正公差用符号变量表示公差不写死这张表是我在给别人做 Code Review 时常用的查错清单。每次发现某段“等差数”逻辑有问题我都会下意识地先过一遍这些选项往往几秒钟就能锁定问题所在。7.3 排查思路从复现到二分当代码逻辑复杂、错误不明确时我的排查步骤通常是这样的第一步复现最小用例。把可能导致问题的输入缩小到最简比如数组长度只留 3 个元素或者只跑一轮循环。这样能把干扰因素降到最低。第二步加日志输出中间变量。尤其是动态规划解法里把每个dp[i][d]的值打出来对照手算结果能快速定位是哪一步的状态转移算错了。在实际工程中我也会用类似的“打点”方式——在数据处理管道中输出每个阶段的样本而不是只看最终结果。第三步二分定位。如果一个长数组的结果不正确我在调试时会把数组一分为二分别判断前半段和后半段是否符合等差数列再逐步缩小异常段的范围。这个过程类似二分查找定位效率很高。不过要注意等差数列的判断并不具备“子区间正确则整体正确”的性质所以你二分时应该找的是“第一个导致公差变化的位置”而不是简单地递归验证两半各自是否等差。8. 实战演练两个综合性案例8.1 案例一统计某一范围内所有等差数假设题目是这样的给定范围[L, R]要求输出该范围内所有长度为 3 的等差数这里“等差数”可能指三位数百位、十位、个位构成等差数列。例如123百位 1、十位 2、个位 32-1 3-2是等差数135也是111也是因为公差为 0124不是因为2-114-22不相等。解法很简单枚举L到R之间的每个三位数拆出各数位判断是否等差。但这个题最大的价值在于“三位数”这个限制。如果题目没有限制位数那复杂度就变成组合问题了。下面给出一个标准实现def is_number_arithmetic(x): s str(x) if len(s) 3: return False d int(s[1]) - int(s[0]) for i in range(2, len(s)): if int(s[i]) - int(s[i-1]) ! d: return False return True def find_arithmetic_numbers(L, R): res [] for x in range(L, R 1): if is_number_arithmetic(x): res.append(x) return res这个实现里需要注意两点第一str(x)之后可以直接按索引取字符但记得要转成 int 再相减否则字符相减会得到 ASCII 差得到的不是数字差。很多语言如 Python 里字符相减是不直接支持的C 里2 - 1等于 1这个成立是因为 ASCII 码连续但容易让初学者误解。推荐显式转换。第二这个暴力枚举的时间复杂度是 O(n * k)其中 k 是位数。对于范围很大的情况还可以进一步优化直接枚举公差和首位数构造三位数然后判断是否在[L, R]内。这样可以把枚举规模从(R-L1)降到9 * 9百位 1~9公差 -9~9是常数级别。这就是“从验证思维”切换到“构造思维”的典型案例。8.2 案例二数组中包含等差三元组的统计再考虑一个更接近真实竞赛的题给定一个整数数组统计其中有多少个三元组(i, j, k)满足i j k且arr[i] arr[k] 2 * arr[j]。这个条件等价于arr[i], arr[j], arr[k]构成等差数列只是换了表达形式。我第一眼看到这种题很多人会写三循环 O(n^3)但 n 到 10^3 就超时。标准做法是枚举中间元素j然后用哈希表记录左侧元素出现情况再扫描右侧元素进行匹配def count_arithmetic_triplets(arr): from collections import defaultdict n len(arr) left defaultdict(int) right defaultdict(int) for v in arr: right[v] 1 count 0 for j in range(n): right[arr[j]] - 1 for i in range(j): left[arr[i]] 1 # 实际更高效的写法见下方 # 更直接的做法先收集左侧再对每个右侧元素匹配 for k in range(j1, n): target 2 * arr[j] - arr[k] if left[target] 0: count left[target] for i in range(j): left[arr[i]] - 1 return count这段代码我写的时候故意保留了“先加再减”的对称结构便于理解思路但实际可以优化成“在遍历 j 的过程中维护左右两个哈希表”减少循环次数。这里留给读着自己尝试改进。核心思想是枚举中间项借助哈希表把两端的匹配查询从 O(n) 降至 O(1)整体 O(n^2) 可过 n 5000 的数据规模。这个“枚举中间项 哈希表维护两侧”的套路远远比暴力三层循环高效而且不止适用于等差三元组很多与“中间项”有关的统计题都能用。9. 工具与工程实践中的“等差数”9.1 在数据处理管道中如何检测等差片段离开竞赛场景等差数列的概念在真实工程里也有不少落点。我最常遇到的一个场景是时序数据中存在某种规律性的递增或递减比如传感器每 5 秒上报一次数据正常情况下数值变化呈线性一旦出现掉线、卡顿或重复上报数值变化规律就会被破坏。此时检测“等差片段”就成了一种数据质量校验手段。实现上我会先做差分diff[i] data[i1] - data[i]。如果数据是等差的那么diff数组应当全部相同如果出现了不同的 diff 值说明数据规律被破坏需要进行告警或插值处理。这个差分方法 O(n)而且可以用流式方式处理不需要一次性加载全部数据。9.2 测试用例设计的通用思路给“等差数”相关函数写单元测试时我会强制自己覆盖以下这几类用例长度为 0 的空序列长度为 1 的序列长度为 2 的序列公差为 0 的恒定序列公差为正、负的普通序列含极大整数或极小整数的序列检查溢出乱序输入但恰为等差序列例如[3, 1, 2]不是等差但[1, 2, 3]是。这些边界用例不是我拍脑袋想出来的而是在多次项目迭代、线上故障排查里逐渐积累的。我见过太多测试用例只覆盖“正常情况”一进入边界就全线崩溃。所以现在养成了“边界优先”的测试习惯先写边界用例再写正常用例。顺序反过来容易因为正常用例全过而过度自信忽略边界。建议如果你时间有限最少也要覆盖“空数组”、“单元素”、“公差为零”、“负公差”、“极大数值”这五类。五类都过了这道题的基本可靠性就有保障了。10. 总结与经验体会要说“等差数”这个话题公式本身确实简单但围绕它的变体非常多从 O(1) 公式、O(n) 判断、O(n^2) 计数到构造类问题每一层都有值得注意的细节。我自己做这个专题时最大的感受是真正难的从来不是等差数列的定义而是对边界条件的敏感度和解题策略的选择。在各类问题里反复出现的关键点无非就是这几个是否要先排序、是否要特判短序列、是否要用整数运算避免浮点误差、是否要枚举中间项配合哈希表。把这些点刻在脑子里不管你遇到的是“问题 N: 等差数”的哪个版本都能快速找到方向。最后再分享一个小技巧如果你在面试或比赛现场卡住了不妨把所有公差相关的计算都用“比较两个差值是否相等”来代替“计算公差并比较是否相同”。比如判断三项a, b, c是否等差直接写2*b a c避免减法可能带来的大整数运算也减少一次变量定义。这个细节看似微小但在高密度编码时能省下不少心智负担。我的建议是找个在线评测平台把这类题目集中刷上十道左右每一道都按“先分类、再定方案、再写边界用例、最后实现”的流程走一遍等差数列这块就算彻底吃透了。方法再好也得自己动手跑几轮才能真正变成你的东西。
1. 问题拆解与思路选择1.1 先说清楚这道题到底在考什么“问题 N: 等差数”这个标题本身很简单但恰恰是这种极简的题目名放在任何一场竞赛、考试或算法练习里都可能对应着三种截然不同的问法给定首项、公差、项数让你输出等差数列的某一项或前 N 项之和给定一个数列判断它是不是等差数列在一个区间或序列中统计满足等差性质的子序列/子数组数量。我在实际带项目、做算法题解时见过太多次这种“极简标题陷阱”很多人一看到“等差数”三个字条件反射就去套a_n a_1 (n-1)*d这个公式结果题目真正考察的是后面两种——判断和计数。所以我每次拿到这种题目第一件事永远是先把题目原文完整读三遍搞清楚输入输出和边界条件再去动笔写公式。这篇文章不针对某一场具体比赛的某个版本而是把“等差数”这类问题背后的通用套路拆开讲透覆盖从 O(1) 公式计算到 O(n^2) 区间枚举的常见解法。无论你遇到的是哪种变体都能在这篇文章里找到对应的思考路径。1.2 为什么这类题目容易“翻车”等差数列是中学数学就讲过的基础概念按理说难度不高但实际做题时翻车率却很高。我总结下来主要有三个原因第一很多人忽略整数溢出问题。题目通常不会给你温馨提醒“答案可能超过 int 范围”但实际数据里首项 10^9、公差 10^9、项数 10^5 的组合非常常见前 N 项和用 int 存直接就溢出了。我见过太多人在这一步吃亏。第二判断等差时只检查相邻两项差值忽略了空序列、单元素序列、重复元素序列等边界。空集和单元素集在数学定义上算不算等差数列不同题目约定不同但很多人压根没意识到要去读题面里关于这个的定义。第三计数类变体特别容易写出 O(n^3) 的暴力代码样例能过一提交就超时。这类题表面上是“等差数”实际上考察的是枚举技巧和哈希表优化。2. 核心概念与基础知识补充2.1 等差数列的三种等价判定方式在动手写代码之前有几个基础知识点值得先明确。判断一个序列是否为等差数列可以用三种等价的视角第一种是递推视角对于连续三项a, b, c满足b - a c - b即2*b a c。这个形式在很多题目里更实用因为避免了一次减法某些语言里可以减少大整数运算的精度问题。第二种是通项视角如果已知首项a_1和公差d那么第 n 项就是a_n a_1 (n-1)*d。这个用于直接求某一项非常快时间复杂度是 O(1)。第三种是求和视角前 n 项和等于n * (a_1 a_n) / 2或者n * a_1 n*(n-1)*d/2。这个公式不仅用于求值还经常反过来用——给你一个和让你反推是否存在某个等差数列满足条件这类题在数论和构造题里非常常见。这三种视角没有优劣之分关键是看题目给的已知条件是什么。如果已知首项和公差就用通项公式如果已知前几项需要判断等差就用递推视角如果已知总和需要反推就用求和公式配合整除判断。2.2 常见变体的识别方法我把“等差数”相关的题目粗略分成四类每一类的解题策略完全不同类型典型问法核心方法时间复杂度求项/求和求第 n 项、前 n 项和公式直接计算O(1)判断判断给定序列是否为等差遍历相邻差O(n)构造给定若干条件构造等差序列数学推导枚举O(n) 或 O(n^2)计数统计等差子序列/子数组数量动态规划/哈希表O(n^2)拿到题目后先分类再决定用什么思路。这听起来像废话但我见过很多人在“求项”的题里非要写个循环迭代或者在“判断”的题里先去排序——排序会把原有顺序破坏掉判断结果自然是错的这就是典型的思路没有先跟上。3. 基础实现求第 n 项与前 n 项和3.1 直接套公式的写法如果你遇到的“等差数”题目是最基础的版本——给定首项a1、公差d和项数n让求第n项或前n项和那么直接用公式就行没什么好犹豫的。下面给出一个同时支持两种查询的示例代码def arithmetic_sequence(a1: int, d: int, n: int): # 第 n 项 an a1 (n - 1) * d # 前 n 项和 sn n * (a1 an) // 2 return an, sn print(arithmetic_sequence(2, 3, 5)) # 第5项14前5项和40这段代码看起来简单但有几个细节值得展开讲。第一个细节是// 2的除法时机。前 n 项和公式n * (a1 an) / 2里的除法推荐全部乘完再做整除而不是边乘边除。原因有两个一是避免浮点数精度问题二是保证结果是整数。很多语言里如果写成(n / 2) * (a1 an)当n是奇数时先除会得到小数后续乘以整数结果可能就出现了精度偏差。第二个细节是数据类型的长度。Python 的 int 是无限精度的写这段代码不会遇到溢出问题。但如果你用的是 C 或 Java就必须小心中间结果n * (a1 an)可能远超最终答案的范围。比如a110^9, d10^9, n10^5时an是10^14级别n * (a1 an)是10^19级别已经超出 64 位有符号整数的最大值约9.2 * 10^18。稳妥的做法是用__int128C或BigIntegerJava或者先用公式变形减少中间量。第三个细节是公差的符号。等差数列的公差不一定是正的可以是负数、零甚至题目可能故意给一个递减序列。a1 10, d -2, n 4时第 4 项是4前 4 项和是28这些情况代码都能正确处理但如果你在公式里写成了a1 (n 1) * d或者n * (a1 an) / 2 1这种“微调”版本就会在负数公差上出问题。所以公式本身不要乱改符号全部由参数决定。3.2 边界条件与隐藏坑位基础题目虽然直接套公式但边界条件仍然值得单独拿出来说。n 0的情况。数学上空序列的前 0 项和定义为 0但第 0 项是什么有的题目约定第 0 项就是首项有的题目不允许查询第 0 项。我建议代码逻辑上做一层防御如果n 0返回 0 或抛出异常不参与公式计算。这种防御不仅让代码更健壮也能防止在实际工程中被上游调用的脏数据打崩。d 0的情况。所有人看到这个第一反应是“全部相等仍然是等差数列”这个没错。但注意如果题目要求“严格等差”即相邻两项差值必须非零那么d 0会被排除在外。考试和面试里经常在这个点上设陷阱。你需要看题目里有没有出现“严格”两个字。a1 an的奇偶性问题。我们使用整除公式时有一个隐含前提n * (a1 an)必须是偶数。这其实自动成立因为等差数列前 n 项和一定是整数。但在构造类题目中如果你手算推导出一个类似x n*(ab)//2的公式而这个公式本身并不保证整除那么就需要用if判断一下能否整除否则不能直接用这个公式构造。注意我在实际做题和写工程代码时有一个习惯——写完公式后用最简单的用例验证一遍a11, d1, n5结果应该是第 5 项等于 5前 5 项和等于 15。这个用例花不了一秒钟但能拦住 90% 的低级笔误。4. 判断一个序列是否为等差数列4.1 常规判断与陷阱再来说第二种常见版本给你一个长度为 n 的数组判断它是否构成等差数列。最直接的办法是先把数组长度n和元素取出如果n 2直接返回 True——因为任意两个数都可以看作是等差数列或者按题面约定空/单元素也成立。然后遍历一次计算arr[1] - arr[0]作为公差d再逐个检查arr[i] - arr[i-1]是否等于d。def is_arithmetic(arr): n len(arr) if n 2: return True d arr[1] - arr[0] for i in range(2, n): if arr[i] - arr[i-1] ! d: return False return True这段代码时间复杂度 O(n)是标准解法。但我要提一个非常容易被忽视的点不能先排序再判断。我遇到过不止一次有同学把数组先sort()一下然后判断相邻差值是否相等。排序会改变元素的原始顺序而等差数列对顺序非常敏感。比如[2, 4, 6, 3, 5]排序后是[2, 3, 4, 5, 6]相邻差值都是 1判断结果是 True但原始序列[2, 4, 6, 3, 5]并不是等差。所以这个坑一定不要踩。如果题目要求判断“无序数组能否重排成等差数列”那才需要排序这是另一回事。判断的关键词是“重排”还是“原来的顺序”。这两个词差了十万八千里。4.2 更快的判断思路在工程场景中有时会遇到超大规模数组比如上亿条的时序数据你想快速知道是否存在某个连续子段是等差的。这时候 O(n) 的遍历虽然已经是线性但配合滑动窗口和剪枝还能进一步提速。一个常见的优化思路是如果数组的长度很长而题目允许只判断整个数组是否为等差那么可以先用开头两个元素求公差然后再扫描。这里不存在理论上的更快算法——因为判断本身需要读一遍所有元素O(n) 已经是最优。但在特定场景下可以用“抽样预检”做启发式优化先检查arr[0], arr[1], arr[2]是否等差再检查arr[0], arr[1], arr[n//2]是否满足通项公式。如果抽样不满足就可以提前结束避免全量扫描。这个技巧在面试的 System Design 讨论里反而经常出现——它并不是理论最优但在大数据量下能显著减少平均扫描时间。我个人的建议是如果是在竞赛或刷题场景老老实实全量遍历即可不要炫技如果是处理真实的海量数据抽样预检值得一试。两者目标不同优化思路也要跟着调整。5. 进阶变体等差子序列的计数5.1 暴力枚举的问题“等差数”题目中最棘手也最常考的变体是“给定一个数组统计其中等差子序列或等差子数组的个数”。先说子数组版本。子数组要求连续暴力思路是枚举所有起点i和终点j然后判断arr[i:j1]是否等差时间复杂度 O(n^3)。n100时勉强能跑n1000就开始卡n10^4以上必然超时。优化到 O(n^2) 的思路很清晰固定起点i逐步扩展终点j同时维护当前的公差。当加入新元素arr[j]时只要arr[j] - arr[j-1]仍然等于当前公差那么这个子数组就是等差的计数加一一旦不等于就 break因为再往后也不可能恢复连续等差。def count_arithmetic_subarrays(arr): n len(arr) count 0 for i in range(n): if i 2 n: break d arr[i1] - arr[i] count 1 # 长度为2的子数组也计入的话 for j in range(i2, n): if arr[j] - arr[j-1] d: count 1 else: break return count这段代码用了“只考虑长度至少为 2 的子数组”的约定。实际题目里单元素子数组是否计入需要看题面不同题目约定不同。我个人写代码时习惯把“长度 1 的子数组”作为特殊情况在开头单独讨论不要混进主逻辑容易乱。5.2 不连续子序列的计数动态规划与哈希表如果是统计不连续的子序列元素不一定相邻但相对顺序不变问题难度就上一个台阶。此时[1, 2, 3, 4]中的[1, 3]也可以构成等差子序列公差 2[1, 2, 3]是等差[1, 2, 4]不是。经典的解法是动态规划 哈希表。定义dp[i][d]表示以位置i结尾、公差为d的等差子序列数量。对于固定的i遍历所有j i计算出d arr[i] - arr[j]然后dp[i][d] dp[j][d] 1其中1表示新形成的长度为 2 的子序列[j, i]最终答案累加所有dp[i][d]同时可以根据需要减去长度为 2 的序列数量。这个解法的时间复杂度是 O(n^2)空间复杂度也是 O(n^2)哈希表的键数量可能有 O(n^2) 种。但对于数据规模中等比如n 2000的题目完全够用。def count_arithmetic_subsequences(arr): n len(arr) from collections import defaultdict dp [defaultdict(int) for _ in range(n)] total 0 for i in range(n): for j in range(i): d arr[i] - arr[j] dp[i][d] dp[j][d] 1 total dp[i][d] # total 包含所有长度2的子序列 return total这里有个容易出现的小偏差total把所有长度为 2 的序列也计入了而长度为 2 的任意两个元素都可以视为等差数列所以如果你最后想统计的是“长度至少为 3”的子序列需要在累加时减去n*(n-1)//2或者只在dp[j][d] 0时才把当前的dp[i][d]加入答案。两种做法都对但一定要保持一致不要混着用。5.3 为什么不用二维数组代替哈希表有人会问公差d的范围如果不大直接用二维数组dp[n][范围]是不是更快理论上如果d的范围有限且可预估用数组确实比哈希表快。但实际题目的数据范围经常把公差范围拉得很大比如arr[i]在[-10^9, 10^9]之间公差范围就有2*10^9 1种可能二维数组根本开不下。这时候必须用哈希表让键只存储实际出现的公差。另外用哈希表存公差还有一个隐藏好处负数公差和零公差都可以作为键直接存储不需要做下标偏移。如果你非要用数组还得额外写一个d offset的映射逻辑一旦忘了处理负数程序就会越界崩溃。这也是我不建议用数组的原因。6. 构造类变体给定条件反推等差数列6.1 常见构造思路另一种“等差数”题目偏向数学构造。典型的问法包括给定首项和末项以及项数 n是否存在一组合法的整数公差给定若干项的约束例如第 2 项和第 5 项的值能否唯一确定整个等差序列将一个整数 n 拆成若干项等差数之和问有哪些拆法。这类题的核心是反推公差。比如给定首项a1、末项an和项数n求解公差的公式是d (an - a1) / (n - 1)判断是否有整数解的条件是(an - a1) % (n - 1) 0。这个取模判断非常关键因为题目通常要求每一项都是整数。不能整除时直接返回“不存在合法序列”。def try_construct(a1, an, n): if n 0: return None if n 1: return [] if a1 an else None if (an - a1) % (n - 1) ! 0: return None d (an - a1) // (n - 1) return [a1 i * d for i in range(n)]这个代码的逻辑很直接但我要强调一个隐含的边界如果n 1那么n - 1 0做除法会直接报错或返回无穷大。所以必须先特判。我见过不少人在 LeetCode 风格的题目里踩这个雷导致边界用例直接 Runtime Error。6.2 多条件下的公差不唯一问题还有一种更复杂的构造场景题目只告诉你“某几项的值”但没告诉你它们分别对应第几项而是给你一个无序的多重集合让你判断能否把这些数排成一个等差数列。这个问题的经典解法是先排序然后用首尾元素推导公差。但也有例外——如果集合里有重复元素排序后首尾元素可能无法唯一确定公差。比如集合[2, 2, 2, 4]排完序后首项 2、末项 4、长度 4公差算出来是(4-2)/(4-1)不是整数按公式判断不存在。但实际上[2, 2, 2, 4]明显不是等差前面三个相同最后突变。所以这里的“按公式计算”仍然有效因为它要求的是整个集合能构成一个等差数列而不仅仅是首尾匹配。但假如集合是[1, 3, 5, 7]显然可以组成公差 2 的等差。此时首尾公式给出的公差是(7-1)/(4-1)2与直觉一致。真正棘手的情况是集合中存在重复元素且长度较大时你可能会被“公差是否是整数”这个条件骗到。例如集合[1, 1, 2, 2]排序后首 1 末 2长度 4(2-1)/(4-1)不是整数所以判断“不可构成等差”——这个结论是正确的。但如果你在代码里把公差算成了浮点数0.333...再拿它去检查其他元素是否匹配就会出现浮点数精度问题可能在特殊用例上报错。因此我总是建议用整数运算加取模判断尽量避开浮点数。7. 常见错误与排查技巧实录7.1 从我自己的踩坑经历说起我第一次在竞赛里被“等差数”题目坑到是一道看似简单的判断题。当时题目给了一个大数组我写完is_arithmetic函数之后本地测试全过一提交就错。反复看了很久才发现问题出在输入格式上——题目里的数组元素是在同一行以空格分隔给出的我用的语言默认按换行读取导致第一个元素读成了整行字符串后续全错。从那之后我养成一个习惯拿到任何输入输出题目先写一个极小的输入样例手动跑一遍输出确信读入逻辑没问题后再写核心算法。这个习惯帮我省下了很多无意义的调试时间。另一个高频错误是忘记考虑n 2的特殊情况。本质上其实是“对题目的边界条件定义不敏感”。比如 LeetCode 上很多题把长度为 0 或 1 的数组视为等差但有些数学定义里空集不一定算。这没有统一标准必须以题面为准。如果题面没说我的默认策略是“保守处理”——把长度小于等于 2 的序列当作等差返回 True但在代码注释里明确标记方便后续产品逻辑修改时快速定位。7.2 典型问题速查表症状可能原因排查方向求和结果比预期大很多中间乘法溢出检查是否使用了足够宽的数据类型结果有小数/浮点误差除法用了浮点改用整数除法并先判断整除判断结果错误先排序丢了原顺序去掉 sort保持原数组顺序计数结果偏多/偏少长度为 2 的子序列是否计入没统一明确约定并保持计算一致边界用例崩溃n0 或 n1 时除零提前特判长度公差为负数时结果错误公式或逻辑中假设了正公差用符号变量表示公差不写死这张表是我在给别人做 Code Review 时常用的查错清单。每次发现某段“等差数”逻辑有问题我都会下意识地先过一遍这些选项往往几秒钟就能锁定问题所在。7.3 排查思路从复现到二分当代码逻辑复杂、错误不明确时我的排查步骤通常是这样的第一步复现最小用例。把可能导致问题的输入缩小到最简比如数组长度只留 3 个元素或者只跑一轮循环。这样能把干扰因素降到最低。第二步加日志输出中间变量。尤其是动态规划解法里把每个dp[i][d]的值打出来对照手算结果能快速定位是哪一步的状态转移算错了。在实际工程中我也会用类似的“打点”方式——在数据处理管道中输出每个阶段的样本而不是只看最终结果。第三步二分定位。如果一个长数组的结果不正确我在调试时会把数组一分为二分别判断前半段和后半段是否符合等差数列再逐步缩小异常段的范围。这个过程类似二分查找定位效率很高。不过要注意等差数列的判断并不具备“子区间正确则整体正确”的性质所以你二分时应该找的是“第一个导致公差变化的位置”而不是简单地递归验证两半各自是否等差。8. 实战演练两个综合性案例8.1 案例一统计某一范围内所有等差数假设题目是这样的给定范围[L, R]要求输出该范围内所有长度为 3 的等差数这里“等差数”可能指三位数百位、十位、个位构成等差数列。例如123百位 1、十位 2、个位 32-1 3-2是等差数135也是111也是因为公差为 0124不是因为2-114-22不相等。解法很简单枚举L到R之间的每个三位数拆出各数位判断是否等差。但这个题最大的价值在于“三位数”这个限制。如果题目没有限制位数那复杂度就变成组合问题了。下面给出一个标准实现def is_number_arithmetic(x): s str(x) if len(s) 3: return False d int(s[1]) - int(s[0]) for i in range(2, len(s)): if int(s[i]) - int(s[i-1]) ! d: return False return True def find_arithmetic_numbers(L, R): res [] for x in range(L, R 1): if is_number_arithmetic(x): res.append(x) return res这个实现里需要注意两点第一str(x)之后可以直接按索引取字符但记得要转成 int 再相减否则字符相减会得到 ASCII 差得到的不是数字差。很多语言如 Python 里字符相减是不直接支持的C 里2 - 1等于 1这个成立是因为 ASCII 码连续但容易让初学者误解。推荐显式转换。第二这个暴力枚举的时间复杂度是 O(n * k)其中 k 是位数。对于范围很大的情况还可以进一步优化直接枚举公差和首位数构造三位数然后判断是否在[L, R]内。这样可以把枚举规模从(R-L1)降到9 * 9百位 1~9公差 -9~9是常数级别。这就是“从验证思维”切换到“构造思维”的典型案例。8.2 案例二数组中包含等差三元组的统计再考虑一个更接近真实竞赛的题给定一个整数数组统计其中有多少个三元组(i, j, k)满足i j k且arr[i] arr[k] 2 * arr[j]。这个条件等价于arr[i], arr[j], arr[k]构成等差数列只是换了表达形式。我第一眼看到这种题很多人会写三循环 O(n^3)但 n 到 10^3 就超时。标准做法是枚举中间元素j然后用哈希表记录左侧元素出现情况再扫描右侧元素进行匹配def count_arithmetic_triplets(arr): from collections import defaultdict n len(arr) left defaultdict(int) right defaultdict(int) for v in arr: right[v] 1 count 0 for j in range(n): right[arr[j]] - 1 for i in range(j): left[arr[i]] 1 # 实际更高效的写法见下方 # 更直接的做法先收集左侧再对每个右侧元素匹配 for k in range(j1, n): target 2 * arr[j] - arr[k] if left[target] 0: count left[target] for i in range(j): left[arr[i]] - 1 return count这段代码我写的时候故意保留了“先加再减”的对称结构便于理解思路但实际可以优化成“在遍历 j 的过程中维护左右两个哈希表”减少循环次数。这里留给读着自己尝试改进。核心思想是枚举中间项借助哈希表把两端的匹配查询从 O(n) 降至 O(1)整体 O(n^2) 可过 n 5000 的数据规模。这个“枚举中间项 哈希表维护两侧”的套路远远比暴力三层循环高效而且不止适用于等差三元组很多与“中间项”有关的统计题都能用。9. 工具与工程实践中的“等差数”9.1 在数据处理管道中如何检测等差片段离开竞赛场景等差数列的概念在真实工程里也有不少落点。我最常遇到的一个场景是时序数据中存在某种规律性的递增或递减比如传感器每 5 秒上报一次数据正常情况下数值变化呈线性一旦出现掉线、卡顿或重复上报数值变化规律就会被破坏。此时检测“等差片段”就成了一种数据质量校验手段。实现上我会先做差分diff[i] data[i1] - data[i]。如果数据是等差的那么diff数组应当全部相同如果出现了不同的 diff 值说明数据规律被破坏需要进行告警或插值处理。这个差分方法 O(n)而且可以用流式方式处理不需要一次性加载全部数据。9.2 测试用例设计的通用思路给“等差数”相关函数写单元测试时我会强制自己覆盖以下这几类用例长度为 0 的空序列长度为 1 的序列长度为 2 的序列公差为 0 的恒定序列公差为正、负的普通序列含极大整数或极小整数的序列检查溢出乱序输入但恰为等差序列例如[3, 1, 2]不是等差但[1, 2, 3]是。这些边界用例不是我拍脑袋想出来的而是在多次项目迭代、线上故障排查里逐渐积累的。我见过太多测试用例只覆盖“正常情况”一进入边界就全线崩溃。所以现在养成了“边界优先”的测试习惯先写边界用例再写正常用例。顺序反过来容易因为正常用例全过而过度自信忽略边界。建议如果你时间有限最少也要覆盖“空数组”、“单元素”、“公差为零”、“负公差”、“极大数值”这五类。五类都过了这道题的基本可靠性就有保障了。10. 总结与经验体会要说“等差数”这个话题公式本身确实简单但围绕它的变体非常多从 O(1) 公式、O(n) 判断、O(n^2) 计数到构造类问题每一层都有值得注意的细节。我自己做这个专题时最大的感受是真正难的从来不是等差数列的定义而是对边界条件的敏感度和解题策略的选择。在各类问题里反复出现的关键点无非就是这几个是否要先排序、是否要特判短序列、是否要用整数运算避免浮点误差、是否要枚举中间项配合哈希表。把这些点刻在脑子里不管你遇到的是“问题 N: 等差数”的哪个版本都能快速找到方向。最后再分享一个小技巧如果你在面试或比赛现场卡住了不妨把所有公差相关的计算都用“比较两个差值是否相等”来代替“计算公差并比较是否相同”。比如判断三项a, b, c是否等差直接写2*b a c避免减法可能带来的大整数运算也减少一次变量定义。这个细节看似微小但在高密度编码时能省下不少心智负担。我的建议是找个在线评测平台把这类题目集中刷上十道左右每一道都按“先分类、再定方案、再写边界用例、最后实现”的流程走一遍等差数列这块就算彻底吃透了。方法再好也得自己动手跑几轮才能真正变成你的东西。
