最近在帮几个学弟学妹备战大厂暑期实习笔试聊到阿里工程岗4月8日那场笔试题时大家普遍反映第三题“相邻等值对贡献和”看着不难但真正动手写的时候却容易卡住。这道题很有意思它不考什么冷门数据结构也不考复杂的算法模板核心就是一道“想明白就秒杀、想不明白就超时”的思维模拟题。今天我把这道题的完整思路、Java/C/Python三种语言的写法以及我在实际调试中踩过的坑都整理出来给正在刷题备战的同学们一份可以直接抄作业的参考。先说结论这道题只要理解了“单点修改只会影响局部相邻关系”这个关键点代码量其实非常小三种语言的核心逻辑都在二十行以内。但恰恰是这层窗户纸很多人现场没捅破硬生生写成每次修改都全数组重新遍历复杂度直接爆炸。下面我把题目还原、思路推导、代码实现和常见坑位一步步拆开讲清楚。1. 题目理解与考点剖析1.1 题目描述还原我根据同学们考后的回忆把题目核心信息还原如下细节表述可能和原题有出入但考点和思路是一致的给定一个长度为n的整数数组a下标从1开始。定义对于任意满足1 i n且a[i] a[i 1]的相邻下标对(i, i1)称为一个“相邻等值对”它的贡献值为下标i。整个数组的“相邻等值对贡献和”就是所有相邻等值对下标i的加总sum。现在有q次操作每次操作给出两个整数pos和val表示把a[pos]的值修改为val。每次修改之后需要输出当前整个数组的相邻等值对贡献和。举个例子输入 5 3 1 2 2 3 3 2 3 3 3 5 1 输出 4 9 5初始数组是[1, 2, 2, 3, 3]其中a[2] a[3]贡献下标2a[4] a[5]贡献下标4所以初始贡献和是6。第一次修改把a[2]改成3数组变成[1, 3, 2, 3, 3]此时只有a[4] a[5]贡献和为4。第二次修改把a[3]改成3数组变成[1, 3, 3, 3, 3]此时a[2] a[3]、a[3] a[4]、a[4] a[5]三对都成立贡献和是2 3 4 9。第三次修改把a[5]改成1数组变成[1, 3, 3, 3, 1]此时贡献和是2 3 5。注意这里的贡献值是下标i而不是固定为1。如果题目改成每对等值对贡献都是1核心解法完全一样只需要把累加的量从i改成1即可。后面的实现我会用“下标贡献”这个版本讲因为它更贴合“贡献和”这个题眼稍微有一点点区分度。1.2 这道题真正在考什么很多同学一看到这题第一反应是“这不就是遍历数组统计嘛”然后唰唰唰写了个双重循环每次修改后重新把整个数组扫一遍统计所有a[i] a[i1]的位置累加下标输出。这做法对不对逻辑上完全对但性能上就是灾难。n和q的范围题目一般不会给得太小在阿里的笔试里这种题的n和q大概率会跑到1e5甚至2e5级别。如果每次修改都O(n)遍历总复杂度O(nq)就是1e10量级随便哪个评测机都扛不住运行超时基本是板上钉钉的。所以这道题真正的考点不是“你会不会统计相邻相等元素”而是“你能不能发现单点修改对全局答案的影响其实是有限的”。换句话说它考察的是局部变更对全局状态影响范围的洞察力这是很多工程场景里非常核心的思维习惯——改了一个变量哪些依赖它的结果会变哪些不会变你心里得有一本账。另外它也考察基本的贡献转换思想全局答案可以拆成若干个局部贡献之和而局部贡献只在特定条件下发生变化维护起来自然就快。这种思想在LeetCode上也经常出现比如那些“翻转一段区间后求总和”的题目套路都是一样的。2. 从暴力到O(1)更新解题思路拆解2.1 暴力做法为什么会被卡先把最直白的暴力思路写出来方便大家对照每次修改完从i 1到n - 1遍历如果a[i] a[i1]就把i加到答案里然后输出。这个写法的复杂度是O(nq)以n 1e5、q 1e5举例总的判断次数是1e10次。现代CPU每秒大概执行1e8到1e9次简单操作一个测试点就要跑几十秒甚至几分钟。笔试系统通常单个用例限制1到2秒所以暴力代码交上去就是TLE没有任何侥幸空间。有同学可能会想能不能用前缀和或者树状数组优化前缀和预处理确实能把单次查询优化到O(1)但问题在于每次修改后前缀和数组本身也要重新算算一次依然要O(n)本质上没有优化。树状数组可以做区间求和但前提是你能找到一种方式让每次修改只影响O(log n)以内的数据项。这道题确实存在这样的结构但不需要把线段树树状数组搬出来因为影响范围比log n还小只有常数个位置。2.2 单点修改的影响范围现在我们掰开揉碎来分析当a[pos]发生改变时哪些相邻等值对的状态可能受影响相邻等值对一共只有n - 1对分别是(1,2)、(2,3)、...、(n-1,n)。注意a[pos]只出现在以下这些相邻对中作为左元素当pos n时出现在(pos, pos1)这对中作为右元素当pos 1时出现在(pos-1, pos)这对中。所以一个位置被修改最多只会影响两对相邻关系(pos-1, pos)和(pos, pos1)。其他所有相邻对的两个元素都没变相等关系自然也不会变对应的贡献值不需要动。这里可以打个生活化的比方想象一排灯串每个灯泡之间有一个开关接头。如果你把整排灯串中间某一个灯泡换了那么会受影响的只有这个灯泡和左边灯泡之间的接头、以及这个灯泡和右边灯泡之间的接头。其他所有接头两端的灯泡都没动过开合状态当然不会变。明白了这一点维护答案就变得很简单了预处理先把初始数组的贡献和ans算出来这个需要O(n)。每次修改前把(pos-1, pos)和(pos, pos1)这两对当前的贡献从ans中减掉。修改a[pos]的值。重新检查这两对相邻关系如果它们变成等值对了就把对应贡献加到ans里。输出ans。这样单次修改的时间复杂度是O(1)整个过程是O(n q)跑1e5级别的数据轻轻松松。2.3 贡献值定义变化不影响核心思路这里再展开说一下诸多阿里的同学反馈中这道题具体贡献值的定义可能有不同版本。有的版本是每对相邻等值对贡献1直接输出对的数量有的版本是贡献下标i还有的版本可能是贡献i和i1的和之类的变体。但无论贡献值怎么定义只要每一对(i, i1)的贡献是一个预先可以确定的数比如bound[i]核心维护思想完全一样预处理时把“满足a[i] a[i1]的bound[i]”全部累加进ans修改pos时先把pos附近两对可能存在的贡献从ans中扣除改完值后再把新的两对贡献加回来。所以你在考场上不用纠结题目具体定义的是哪种贡献只需要先明确“每对相邻等值对的贡献是多少”以及“我用的数组下标是1-based还是0-based”剩下的事情就是机械地套这个局部更新模板。这种“剥离开具体数值、抓住增量维护逻辑”的抽象能力往往是笔试能不能快速AC的分水岭。3. 三种语言实现与踩坑点3.1 Java版实现注意读入和长整型Java的代码我放在下面用的是BufferedReader StringTokenizer做输入输出用StringBuilder统一攒着再一次性打印。笔试场景下Java的Scanner读数据太慢遇到大数据量很容易TLE这是老生常谈的坑。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)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); int q Integer.parseInt(st.nextToken()); int[] a new int[n 2]; st new StringTokenizer(br.readLine()); for (int i 1; i n; i) { a[i] Integer.parseInt(st.nextToken()); } long ans 0; for (int i 1; i n; i) { if (a[i] a[i 1]) { ans i; } } StringBuilder sb new StringBuilder(); while (q-- 0) { st new StringTokenizer(br.readLine()); int pos Integer.parseInt(st.nextToken()); int val Integer.parseInt(st.nextToken()); // 先移除旧贡献 for (int i pos - 1; i pos; i) { if (i 1 i n a[i] a[i 1]) { ans - i; } } a[pos] val; // 再添加新贡献 for (int i pos - 1; i pos; i) { if (i 1 i n a[i] a[i 1]) { ans i; } } sb.append(ans).append(\n); } System.out.print(sb); } }这里我用了一个小技巧把“移除旧贡献”和“添加新贡献”都写成循环遍历i pos - 1到i pos这样即使pos在数组边界比如pos1循环里的i会取到0配合i 1的判断直接跳过不会出现数组越界。代码也简洁清晰不用单独写if分支处理头尾特殊情况。为什么ans要声明为long而不是int因为贡献值是下标i的累加极端情况下数组里所有相邻元素都相等也就是n-1对全都贡献那么ans最大是1 2 ... (n-1) n(n-1)/2当n2e5时约为2e10明显超出int范围。笔试里因为溢出吃WA是非常冤的我建议只要看到“和”这种统计一律用long。3.2 C版关闭同步别乱混C版本核心逻辑和Java完全一致最大的区别在于输入输出。我用了ios::sync_with_stdio(false)和cin.tie(nullptr)两行提速这样cin/cout就足够快了。但要特别注意一旦关闭同步代码里就不要再混用scanf/printf否则可能出现诡异的输入错乱。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin n q; vectorlong long a(n 2); for (int i 1; i n; i) { cin a[i]; } long long ans 0; for (int i 1; i n; i) { if (a[i] a[i 1]) { ans i; } } while (q--) { int pos; long long val; cin pos val; for (int i pos - 1; i pos; i) { if (i 1 i n a[i] a[i 1]) { ans - i; } } a[pos] val; for (int i pos - 1; i pos; i) { if (i 1 i n a[i] a[i 1]) { ans i; } } cout ans \n; } return 0; }C的vector默认初始化为0所以开n2大小后a[0]和a[n1]都是0配合边界判断用起来很安全。有人可能会想既然a[0]和a[n1]都是0那如果数组里其他位置也恰好是0会不会误判不会因为边界判断i 1 i n保证了我们永远不会去检查a[0]和a[n1]参与的相邻对这两个哨兵位置纯粹是为了防止数组越界不会进入逻辑判断。3.3 Python版用缓冲区读入Python版本我用sys.stdin.buffer.read()一次把所有输入读进来按空格直接切分成整数列表避免多次调用input()造成性能损耗。这在数据量大的时候效果非常明显。import sys def main(): data list(map(int, sys.stdin.buffer.read().split())) idx 0 n, q data[idx], data[idx 1] idx 2 a [0] * (n 2) for i in range(1, n 1): a[i] data[idx] idx 1 ans 0 for i in range(1, n): if a[i] a[i 1]: ans i out [] for _ in range(q): pos, val data[idx], data[idx 1] idx 2 for i in (pos - 1, pos): if 1 i n and a[i] a[i 1]: ans - i a[pos] val for i in (pos - 1, pos): if 1 i n and a[i] a[i 1]: ans i out.append(str(ans)) sys.stdout.write(\n.join(out)) if __name__ __main__: main()Python版本里我用元组(pos - 1, pos)而不是range循环主要是省去循环变量自增的开销代码也更直观。这里要注意的是Python的int没有溢出问题所以ans随便累加不用担心。3.4 三份代码对比与易错点为了让你一眼看清三种实现的异同我整理了一张对比表。语言核心复杂度主要输入输出处理最容易踩的坑JavaO(n q)BufferedReader StringTokenizerScanner读大数据会TLEans忘用long溢出CO(n q)ios::sync_with_stdio(false)关闭同步后再混用scanf/printf输入乱序PythonO(n q)sys.stdin.buffer.read()用input()逐行读导致TLElist下标写错共同更新时只看pos-1和pos两对边界判断i 1 i n数组下标从0开始还是从1开始搞混这里我特别想多说一句下标的问题。很多算法题默认数组下标从0开始但本题为了贡献值用下标i表示更自然我用的是1-based下标。如果你平时写0-based写习惯了很容易在边界判断上出错。一个保险的做法是不管题目怎么给你在代码里明确注释“a数组下标1..n有效”然后所有循环和判断都围绕这个约定来不要中间切来切去。4. 在线测试与自测用例4.1 手动推演一遍样例题目做完了还需要能自己验证。上面那个样例是我特意挑的它覆盖了好几种情况初始有相邻等值对、修改中间位置、修改末尾位置、修改产生新的连续等值段。我们手动推演一遍顺便帮你验证理解是否正确。初始数组[1, 2, 2, 3, 3]a[2]a[3]贡献2a[4]a[5]贡献4ans6。第一次操作pos2, val3。修改前受影响的是(1,2)和(2,3)两对。当前(1,2)a[1]1, a[2]2不相等贡献0(2,3)a[2]2, a[3]2相等贡献2ans先减去2。修改a[2]3数组变[1,3,2,3,3]。重新检查(1,2)1 ! 3不贡献(2,3)3 ! 2不贡献。ans6-24。输出4。第二次操作pos3, val3。修改前受影响的是(2,3)和(3,4)两对。当前(2,3)a[2]3, a[3]2不相等(3,4)a[3]2, a[4]3不相等所以ans不减。修改a[3]3数组变[1,3,3,3,3]。重新检查(2,3)33加贡献2(3,4)33加贡献3。ans4239。输出9。第三次操作pos5, val1。修改前受影响的是(4,5)这一对因为pos-14pos5但posn时in超出i n限制被跳过实际上只检查(4,5)。当前(4,5)a[4]3, a[5]3相等贡献4ans减去4。修改a[5]1数组变[1,3,3,3,1]。重新检查(4,5)3 ! 1不贡献。ans9-45。输出5。手动推演结果和输出完全一致说明逻辑是对的。4.2 边界用例与自测要点在线测试除了跑题目给的样例我建议你补上这几类边界数据能迅速暴露代码里最常见的隐患n1的情况。此时没有任何相邻对无论怎么修改ans始终为0。代码里预处理循环for (int i 1; i n; i)根本不会执行更新时pos - 1可能等于0pos可能等于1但边界判断会拦下来输出0。修改pos1数组首元素。此时只有(1,2)这一对可能受影响更新循环里的i依次为0和1i0被边界拦掉i1正常检查。修改posn数组末尾元素。此时只有(n-1,n)这一对可能受影响更新循环里的i依次为n-1和nin被i n拦掉。所有位置都相等比如n5, a[7,7,7,7,7]此时贡献和是123410连续修改中间位置观察ans变化能验证减法加法是否成对出现。修改pos后新值恰好和旧值一样。这种情况下先减后加会互相抵消ans不会变。但如果你贪图省事不写“先减后加”改成“先判断新旧是否相同再决定要不要更新”逻辑就容易出bug——因为即使a[pos]没变它和左邻、右邻的相等关系本来就要重新确认写起来反而要嵌套一堆条件分支。所以我推荐统一用“无条件先减、再加”的写法保证逻辑不会漏。5. 常见问题与排查技巧5.1 笔试现场容易踩的坑先说个我见过很多次的错误更新时只减了a[pos]和a[pos1]这一对忽略了a[pos-1]和a[pos]这一对。这样会导致修改后左侧的相邻等值对没有被正确更新样例能过一部分但一跑到中间位置的修改用例就WA。记住a[pos]同时是左右两对相邻关系的参与者漏掉任何一对都不行。第二个高频坑是用int存ans。我前面算过即使n只有2e5贡献和就能到2e10int最大只能表示约2.1e9直接溢出成负数。笔试系统不会提示你“这里该用long”它只会给你一个Wrong Answer排查起来非常浪费时间。第三个坑在Java和Python里格外明显用Scanner和input()逐行读大数据。有些题n和q是2e5输入文件能有几十万甚至上百万个整数Scanner的解析开销很大Python的input()更不用说每调用一次都有系统级开销。如果你的算法没问题却仍然TLE先检查读入方式是不是太慢了。第四个坑是关于更新顺序。一定要牢记先根据旧值减掉可能存在的旧贡献再修改a[pos]最后根据新值添加新贡献。如果先把a[pos]改了再去做减法你减掉的是新值产生的贡献而不是旧值的ans就会错乱。写代码的时候这两步之间不要插入任何其他对a数组的修改。5.2 题目如果想升级怎么办这道题的简单版本是单点修改全局查询。如果面试官或者笔试变体把问题升级比如把“全局查询”改成“区间查询”问你每次修改后输出某个区间[l,r]内相邻等值对的贡献和那原来的O(1)增量维护就不够用了因为你还需要快速回答任意区间的和。这种情况有两条路。一是用前缀和预处理时维护一个前缀贡献数组pre[i]表示前i个相邻位置的总贡献也就是pre[i] pre[i-1] (a[i] a[i1] ? 贡献i : 0)这样查询[l,r]区间内相邻等值对贡献和就是pre[r-1] - pre[l-1]O(1)查询。但缺点也很明显一旦发生单点修改前缀和数组要重新计算退化成O(n)。二是因为有修改更合适的是用线段树或树状数组。每个叶子节点存“当前位置相邻对是否相等产生的贡献”修改a[pos]时更新两个叶子节点pos-1和pos然后向上合并区间和查询和更新都是O(log n)。如果题目数据范围达到1e5甚至1e6log n的复杂度依然轻松应对。不过说实话单点修改全局查询的场景硬上线段树属于杀鸡用牛刀笔试时间有限还是O(1)维护来得干脆。还有一种升级是把“相等”条件改成更复杂的比较规则比如a[i]a[i1]为奇数、a[i]和a[i1]的差的绝对值小于k等等。这种变体下核心的“修改pos只影响pos-1和pos两对”的性质仍然成立你还是可以用维护贡献的方式只是判断条件变了而已。抓住这个性质不管题目怎么包装你都能很快写出更新逻辑。5.3 三种语言在笔试中的选择建议如果让我给建议平时练题用Python最舒服代码短、调试快、不容易因为类型问题翻车很适合快速验证思路。但笔试的时候我更推荐用自己最熟练的语言而不是“理论上最快”的语言。因为考试拼的不只是性能更是你在紧张状态下写对代码的概率。C的优点是运行速度快、模板库齐全但也正因为各种隐式类型转换、指针和迭代器容易出错调试成本高。Java则夹在中间代码量比Python多但比C更容易写出不出错的代码加上JVM的垃圾回收实际运行速度在1e5级别数据下完全没问题。Python的缺点是输入输出慢但配合sys.stdin.buffer.read()基本也能应对大部分笔试数据量。我个人在笔试里一般用Java因为它的长整型明确集合类工具多IO模板我背得很熟遇到这类思维模拟题可以做到“脑中思路清晰手上代码咔咔出”。建议你也在考试前准备好自己的固定输入输出模板Java的BufferedReader模板、C的ios同步关闭模板、Python的buffer读入模板分别背熟一个考场上就不用现场想。最后说点个人经验。我在模拟这道题的时候一开始也走了弯路总想着用Map记录每个相等位置的集合再维护一个有序结构来处理修改写了七八十行代码。后来冷静下来画了个数组下标示意图发现被修改的位置左右各扫一眼就够了根本不需要任何复杂数据结构。很多时候笔试卡住不是因为题目难而是我们下意识地把问题想复杂了。遇到这种“维护全局状态”的题目先停下来说清楚“一次变更会影响哪些局部”往往答案就自己浮出来了。你在考场上如果没思路也可以试试在草稿纸上画一排格子手动模拟一次修改把变化的位置圈出来这比闭着眼睛空想要管用得多。