看到“蓝桥杯2019年Java C组第9题——等差数列”很多人第一反应是这不就是初中学过的等差数列吗有什么难的。结果真上了考场不少人在这一题上栽了跟头。问题恰恰就出在“太熟悉”上——越熟悉的定义越容易让人忽视它在编程题里换了一副面孔。这道题表面上叫“等差数列”实际上考的是数论里的最大公约数再套一层排序和边界情况的处理。题目本身的代码量极短二十行以内就能写完但能不能想到把公差和gcd联系起来决定了你是轻松拿下还是卡到交卷。这篇文章不打算只贴一份能过的代码而是把“为什么这么解”完整讲透再把我在实际调试中遇到的坑和扩展思路一并整理出来。无论你是备赛的选手还是刚接触算法题的新手照着这个思路走一遍都能把这道题吃透。1. 题目内核一道“等差数列”到底在问什么1.1 从题目描述到输入输出的完整翻译题面描述通常比较简洁给定若干个整数这些整数是某个等差数列中的一部分要求找出一个最短的等差数列使其能够包含所有这些给定的数然后输出这个最短数列的长度。这里的“包含”二字是关键它不是说给定的数字必须是连续的几个项而是在原等差数列中可以有缺失的项。比如给定数[2, 6, 10]它可以是公差为4的等差数列的一部分也就是2、6、10三项正好齐全也可以是公差为2的等差数列2、4、6、8、10中间的两个缺失项缺失了。前一种情况下最短长度是3后一种情况就需要包含4和8最短长度变成5。题目要的是包含所有给定数的最短长度这个逻辑关系先要捋清楚否则后面全乱。数据范围方面一般会给出N个正整数N最大能到几万甚至十万级别每个数的大小范围也会给一个上限。看到这个量级基本上可以立刻排除暴力枚举公差的做法——如果对公差从1枚举到最大值复杂度受不了而且公差的上限根本没有明确下界枚举起来又慢又傻还容易漏情况。1.2 第一直觉为什么容易跑偏绝大多数人拿到题的第一步是想着把所有数字排序然后看看相邻数字之差猜一个公差出来。这个方向其实没有错错的是“猜”的方法。我有段时间做题有个坏习惯总喜欢凭感觉找一个最小差值当成公差认为长度就是(max - min) / 公差 1结果一提交就错。原因很简单最小相邻差并不一定是整个数列能共同使用的公差。举一个例子。给定数是[1, 3, 7]排序后相邻差分别是2和4。如果拿最小差值2当公差构造出的序列是1、3、5、7长度4看起来没问题。但如果给定数是[1, 4, 7]相邻差是3和3公差取3长度是3也没问题。但如果给定数是[1, 4, 10]最小差是3拿3当公差根本不成立因为10减1等于99正好是3的倍数4减1等于3还是3的倍数这组数据就好像又能成立实际构造出来是1、4、7、10长度4确实成立。那再换一组[1, 5, 11]最小差是4但11减1等于1010不能被4整除拿4当公差就错了。所以问题的难点就在这你需要找到一个公差d使得任意两个给定数之间的差都能被d整除。也就是说d必须能整除“所有数之间的差”。那这个d到底怎么找答案藏在一个初中就学过、但竞赛题里反复出现的概念里最大公约数。1.3 这道题真正考察的算法能力蓝桥杯这类竞赛C组面向的是入门到进阶的选手第9题通常已经有明显的区分度。“等差数列”这题不属于那种需要几百行代码的大模拟也不依赖复杂的数据结构它就考一件事你能不能在看似熟悉的数学定义里识别出真正的算法模型。这种题型在算法竞赛里有个通称叫“数学思维题”。它不给你现成的模板而是让你通过整除性质、gcd性质、边界讨论把一个看起来像几何级数的问题转化为一个三步就能写完的程序。理解这道题相当于理解了一整类“给出若干离散点求覆盖它们的最稀疏规则网格”的问题。往后做某些关于时间表、坐标系、周期性的题目时你会发现核心思路完全一样。所以别小看这道题它值回票价。2. 关键推论公差为什么是相邻差值的最大公约数2.1 从“包含关系”推出整除关系假设我们排序后的数列是a1, a2, ..., an。题目说这些数在某个等差数列中公差是d那么这个等差数列可以写成首项 k * d其中k是整数。既然每一个给定的ai都是这个等差数列中的项那么对于任意两个给定的数ai和aj它们的差一定满足以下公式aj - ai (kj - ki) * d也就是说任意两个给定数的差值都必须是公差d的整数倍。这个结论非常关键它是整个解题思路的基石。反过来想如果我们要找一个尽可能大的公差d来压缩等差数列的长度那么d必须同时整除所有“两两差值”。在所有能同时整除这些差值的数里最大的那个是什么就是这些差值的最大公约数。于是方向就变得很清晰了先求出所有相邻差值再求这些差值的最大公约数这个gcd就是能用的最大公差。2.2 为什么只看“相邻差”而不看所有两两差有人会问既然要求d整除任意两个数之间的差那我应该把所有的两两差值都算出来再求gcd为什么只看相邻差就够了这个问题的答案是因为gcd具有传递归约的性质。我们先算相邻差b1 a2 - a1, b2 a3 - a2, ..., b(n-1) an - a(n-1)。不难发现任意跨多个位置的差值比如a4 - a1实际上可以写成a4 - a1 (a2 - a1) (a3 - a2) (a4 - a3) b1 b2 b3由于b1、b2、b3每一个都能被d整除它们加起来的和当然也能被d整除。所以只要d能整除每个相邻差它就能自动整除任意两数之差。反过来如果d要整除所有两两差值它至少也要整除相邻差。因此“相邻差的gcd”和“所有两两差的gcd”在效果上是完全一致的但计算量却从O(n^2)降到了O(n)。取所有相邻差的最大公约数本质上是在提取这一组数字的内在“最小步长”。这里还要注意一个容易被忽略的细节差值本身应当是非负的。所以在计算相邻差之前必须排序。如果不排序相邻差会出现负数虽然gcd函数通常也接受负数但负数参与gcd运算容易让代码逻辑变得混乱而且排序本身也是构造等差数列的前提。排序之后后一个数减去前一个数差值永远为正数或零处理起来省心得多。2.3 最短长度公式是怎么来的有了最大公差g之后构造最短等差数列就变得非常简单。从a1到an按照公差g依次展开一共有多少个项因为an - a1必然是g的整数倍所以最短长度就是长度 (an - a1) / g 1加1的原因很简单从起点a1到终点an一共跨越了多少个公差段段数加1才是项数。比如1到10公差为3差值9除以3等于3段数是3项数是4对应1、4、7、10。这个公式在任何等差数列求项数的问题里都一样闭着眼睛都能写。那么有没有可能用一个比gcd更大的公差也能让所有给定的数都落在序列里不可能。因为如果存在更大的公差h那么h就必须同时整除所有的相邻差这与g是“最大公约数”的定义矛盾。如果用一个更小的公差比如g/2长度反而变长了不满足“最短”的要求。也就是说g是该场景下唯一正确的选择它既能覆盖所有给定数据又能让总长度压缩到极限。3. 完整代码与关键切片解读3.1 一段十几行的Java解法话不多说先给出一个简洁、能直接提交的版本。这个版本在实际竞赛里完全够用逻辑清晰也不依赖任何第三方库import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] a new int[n]; for (int i 0; i n; i) { a[i] sc.nextInt(); } Arrays.sort(a); int g 0; for (int i 1; i n; i) { g gcd(g, a[i] - a[i - 1]); } if (g 0) { System.out.println(n); } else { int len (a[n - 1] - a[0]) / g 1; System.out.println(len); } sc.close(); } static int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); } }就这么短。做完排序之后一个循环把相邻差逐一和g做gcd运算最后根据g是否为0来决定输出。你可能觉得这段代码太简单甚至怀疑是不是漏掉了什么复杂情况。实际上没有这道题的核心就在这个gcd里。3.2 gcd的初始化技巧为什么从0开始而不是从第一个差值开始我自己第一次写这题的时候习惯性地先把g初始化为a[1] - a[0]然后再从i2开始循环。那样写当然也没问题但代码会多一个特殊判断而且如果n等于1访问a[1]就直接越界。从0开始初始化则不同这是一个非常实用的技巧任何数x与0求最大公约数结果还是x因为0能被任何非零数整除。于是循环里写的g gcd(g, a[i] - a[i-1])第一次执行时等价于把g直接赋值为第一个相邻差值之后每轮再逐步收敛到所有差值的gcd。这个技巧看起来只是写法上的取巧实际上它规避了两个边界问题一是n等于1时循环不执行g保持0后续能走特判分支二是无需提前取出第一个差值避免数组长度检查。一套操作下来代码反而更鲁棒。关于gcd函数本身上面用的是递归写法。欧几里得算法的原理是gcd(a, b) gcd(b, a % b)一直递归到余数为0此时的被除数就是最大公约数。这个函数必须记住它不仅是本题的核心后面做数论题时还会反复用到。如果担心递归栈深度也可以写成迭代版static int gcd(int a, int b) { while (b ! 0) { int t a % b; a b; b t; } return a; }两种写法效果一样任选其一即可。3.3 输入输出与性能细节这个题的N理论上可能到十万级别如果用Scanner读入其实也能过因为总共就一次排序和一次O(n)循环真正的耗时大头在排序上。但有经验的选手通常会用BufferedReader来读原因很简单比赛环境中输入规模一旦上来Scanner的nextInt方法会因为内部正则解析而产生不小的开销而BufferedReader配合split或自定义读取速度能快不少。下面是常用写法import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int n Integer.parseInt(br.readLine()); String[] parts br.readLine().split( ); int[] a new int[n]; for (int i 0; i n; i) { a[i] Integer.parseInt(parts[i]); } Arrays.sort(a); // 后续逻辑同上 } }这个读法有一个前提输入数据都写在一行用空格分隔。如果题目没说输入格式是一行还是多行保险起见可以用StringTokenizer或者直接逐行读取再合并。对于这道题来说通常不会在这里卡人但保持良好的输入习惯总没有坏处。4. 常见错误与实测排查记录4.1 排序和差值的坑第一种常见的错误是忘了排序。如果数组是乱序的直接计算相邻差值会产生负数。虽然gcd函数能处理负数但求出来的“最大公约数”和长度公式就全乱套了。我见过有人用未排序数组算差值结果得到了一个负数公差然后长度公式算出来是个负数一提交直接Runtime Error或者答案错误。解决办法只有一句先排序再谈公差。第二种错误是想当然地把“第一个差值”当成最终公差。前面已经举过反例当相邻差值不完全一致时第一个差值往往太小不能整除后面更大的差值。正确做法是老老实实把所有相邻差值取gcd而不是中途截断。还有一种情况是数据量很大的时候直接开一个专门存放相邻差值的数组其实没必要因为累gcd并不需要保存历史差值每轮用完即可。我最初写的时候为了“结构清晰”单独开了一个diff数组后来发现纯粹浪费空间。万一N到百万级别这种多余的数组也会带来内存压力。4.2 所有数字相等的特殊分支这个分支最容易丢分。假设输入是5个2也就是[2, 2, 2, 2, 2]排序后所有相邻差值都是0累加gcd后g还是0。如果我们还按长度公式来算那(2-2)/0 1直接除零异常程序崩溃。即便你做了保护改成除以1得到的结果也是1但正确答案却是5。为什么想一下等差数列公差为0时所有项都相等。题目说给定的这些数“是某个等差数列的一部分”那这个数列必须包含5个2。长度为1的等差数列只包含一个元素显然放不下这5个2。长度为5、公差为0的等差数列即2、2、2、2、2是完全合法的。所以最短长度不是1而是n本身。因此代码里的特判g 0时直接输出n既避免了除零也保证了逻辑正确。4.3 int溢出与数据范围预估很多人做简单题习惯全部用int但这题隐藏着一个隐患。题目里给的原始数据可能是int范围内的正整数但相邻两个数的差值也有可能在int范围内用int算长度好像没问题。然而当差值很大且公差很小时比如最大值是1000000000最小值是1公差是1长度就是1000000000这在int范围内倒还好但如果数据再放开一点比如10的9次方量级的数字配合公差1长度刚好卡在int上限附近。更稳妥的做法是用long存储长度和部分变量避免在极端构造数据下溢出。竞赛题目的数据范围通常不会故意卡这个点但“用long不亏”是一个好习惯。尤其是当题目没有明确说明每个数大小上限的时候宁可多用8个字节也不要在边界数据上翻车。我实际测试过把代码里的数组类型保持int、仅把最终长度计算用long的写法也能通过但如果你怕麻烦直接全上long也完全可行。4.4 常见问题速查表现象可能原因修复方法输出结果为负数未排序就计算差值在求差值前调用Arrays.sort输入只有一个数却报错数组越界循环从1开始g初始为0无需直接访问a[1]输出结果等于1未处理g0时全等分支当g0时直接输出n除零异常g0时仍然计算长度先判断g再进入长度公式答案比预期大很多错误地把最小相邻差当公差实际应取gcd将相邻差的gcd作为最大可用公差大样例超时使用了双重循环枚举公因子改为排序后单循环累gcd数据位随意换行导致读取不完整一次性readLine按空格分割换行未被处理使用Scanner或逐行累加读取这张表是我在实际刷题和帮别人排查时总结出来的几乎覆盖了这道题所有的报错类型。如果提交后WA答案错误先别急着怀疑思路按表格逐项对照代码往往一眼就能定位。5. 从一道题延伸到一类题等差数列思维的扩容5.1 变体一乱序数组能否重新排列成等差数列这种题在面试和笔试里同样常见给你一个数组问能否通过重新排列使其变成一个等差数列。解法也不复杂排序计算相邻差检查所有相邻差是否相等。如果相等则能构成等差数列。理解了“公差是相邻差gcd”这道题之后你会发现这个变体其实更简单因为它要求公差必须唯一确定不存在“多个可能公差”的情况。从做题角度来说这个变体提醒我们排序往往是处理数列问题的第一板斧。不管题目问的是“最短包含长度”还是“能否构成”先把无序数据变成有序所有结构才有可能浮现出来。5.2 变体二最长等差子序列如果数据范围缩小到几百题目可以升级为在给定数组中找出最长的等差子序列子序列不要求连续。这时gcd思路就退场了需要动态规划或者哈希表来记录以某个元素结尾、以某个差值为基准的最长长度。比如定义dp[j]表示以第j个元素结尾、公差为d时的长度那么dp[j] dp[i] 1其中a[j] - a[i] d。这里公差d是动态变化的不再统一。从“等差数列”这道题到“最长等差子序列”核心变化在于“所有给定项共用一个公差”变成了“不同位置可用不同局部公差”。这一对比能帮你更清晰地把握原题的限制条件它要求一个全局公差覆盖全部输入因而才能用gcd一锤定音。5.3 变体三超大整数域下的排序选择假设题目把每个数的大小扩大到10的18次方量级排序依然可行但除非数据量非常小否则不适合用Java内置的Arrays.sort处理对象型数组。更科学的做法是用基数排序或者离散化配合索引数组。不过竞赛场景下这种做法极少出现更多是为了练习时间复杂度估算。这道题的教训在这里体现得很明显当数据范围变大时算法的主体逻辑没变变的只是读入、存储和排序这些外围环节。如果你能把核心思路剥离出来就发现无论数据变成什么样都逃不开“排序 相邻差gcd 长度公式”这个骨架。6. 真题刷题方法论如何把一道题的价值榨干6.1 拿到题先做“三问”我刷题有个习惯看到一道蓝桥杯真题不急着看题解先问自己三个问题数据范围多大操作目标是什么有什么限制条件拿这道题来说数据范围决定了不能用O(n^2)枚举操作目标是找到最短长度限制条件是所有给定数必须落在同一等差数列中。这三个问题一问完方向基本就锁死了排序一敲gcd一算公式一填题目就算拿下了。很多同学喜欢一上来就动手写代码结果写到一半发现思路错了又推翻重来。其实多花两分钟做“三问”比多花半小时调试划得来。这道题尤其适合用来练习这种思维流程因为它的代码太短你甚至可以把全部精力放在推理过程上。6.2 复盘时应该记录什么刷完一道题不要急着进入下一道。花十分钟复盘把下面几点记录下来一是“为什么答案是这个公式”二是“我最初想错在哪里”三是“有没有可能把这道题变形成新题”。这三个问题分别对应数学推导、错误修正和思维迁移。坚持几个星期你会发现自己面对新题时第一反应不再是“我怎么没见过”而是“这题像不像之前那道”。就拿“等差数列”来说复盘时如果记下“取最大公约数是求最小公倍步长的关键”那以后再遇到“给定一组时间点求均匀覆盖所有时间点的最小时间表周期”这类题你就能本能地想到gcd。这种迁移能力才是刷真题最大的收获。6.3 我的个人刷题习惯我自己在备赛时会把同一道题用不同语言、不同写法各做一遍。比如这道题先用Java写一遍标准解法再用C写一遍加深对gcd的理解最后试着用最笨的方法——枚举所有可能公差并验证——跑一遍小数据看看暴力解和最优解的差异。这个过程看似浪费时间其实帮你把“为什么非用gcd不可”刻进脑子里而不是只背下一个模板。另外我会刻意把代码里的变量名写得更语义化比如用diffGcd表示累积公差用maxVal和minVal表示排序后的端点。这样回看代码时即使过了几个月也能一眼看出每一步在干什么。比赛中代码写的快当然重要但平时练习时稍微讲究一点长期收益更大。最后再分享一个我踩过几次坑之后总结的小经验在本地测试时除了官方给的样例一定要自己构造几组极端数据比如所有数相同、只有一个数、差值很大但公差为1、数据乱序。每组数据对应一个可能的坑。把这些坑提前踩一遍比赛时就不会被它们绊倒。这道“等差数列”题目虽小但如果你能把它的解题思路、边界讨论、变体迁移全部掌握收获完全不亚于刷三道所谓的大题。