第一次在周赛题单里看到 3371 这道题时我第一反应是“这题估计又是模拟题把数组里的元素试一遍看哪个是离群值”。真动手写才发现如果照着题面去模拟逻辑很容易绕进死胡同。反而是先把题目翻译成一个等式再用“枚举一个变量、用哈希表维护另一个变量的候选集合”这个思路来解代码又短又不容易错。这篇文章就以力扣 3371 为例子把“移项变形”和“枚举右维护左”这两个技巧掰开揉碎讲清楚。内容不光是给答案更会把题目背后的思维过程、边界条件、以及我在实际提交中踩过的坑都过一遍。适合正在刷力扣、准备面试、或者想提升“把文字题变成数学公式再变成代码”能力的朋友。1. 从题目设定到数学关系先把“离群值”翻译成等式1.1 题干到底在讲什么力扣 3371 的题面看起来有点绕数组里有 n 个元素其中恰好 n-2 个是“特殊数字”special numbers。剩下两个元素里一个是“和元素”值等于所有特殊数字的总和另一个才是我们要找的“离群值”outlier。这里很容易产生一个误区以为要先找出哪两个是“剩下的元素”再判断哪个是和元素、哪个是离群值。实际上完全不需要这样。我举个具体例子假设数组是[2, 2, 1]特殊数字只有 1 个值是2和元素的值就是所有特殊数字的和也就是2离群值是1。再比如[3, 3, 6, 4]特殊数字是3, 3, 4和为10和元素是10但数组里没有10所以这个例子不成立。从这个角度看题目的核心并不是“找到哪两个元素比较特殊”而是“判断某个元素是否可能作为离群值同时让其余元素满足‘和元素 特殊数字之和’这一条件”。1.2 移项变形把一段绕口的话变成一行公式如果把条件写成数学式事情会清晰得多。不妨设total是整个数组所有元素的和x是离群值S是所有特殊数字的总和和元素的值就是S。根据题面数组总和total由三部分组成所有特殊数字的加和也就是S和元素本身的值也是S离群值x。所以有total S S x稍微整理一下把x挪到等式左边total - x 2 * S这就是整道题最关键的一步也是标题里“移项变形”指的东西。原来那个“一堆特殊数字加起来要等于某个特殊元素”的表述经过移项之后变成了一个非常干净的判断条件如果某个元素x是离群值那么数组中必须存在另一个元素S使得2 * S total - x。这一步变形的意义在于我们不再需要关心“哪些数字是特殊数字”也不需要去枚举各种子集。只要检查total - x能不能被 2 整除、以及对应的(total - x) / 2是否存在于数组里就够了。1.3 为什么暴力模拟是坏的直觉说实话我第一次看到这题时脑子里冒出的暴力解法是这样的枚举每一个元素假设它是离群值把它从数组里删掉剩下的元素两两组合判断“某个元素能作为和元素其余元素之和等于它”。这个做法有几个问题第一它需要双重枚举复杂度轻松变成O(n^2)在n 10^5的约束下直接超时。第二也是最关键的“删掉离群值后再去找和元素”这种思路会在逻辑上把“和元素”和“特殊数字”对立起来导致忘记一个事实特殊数字的总和可能非常大甚至可能等于和元素本身的值而和元素只是数组中的一个普通元素它跟离群值一样只是一个位置。也就是说暴力模拟的问题在于它把条件当成过程来理解而不是当成等式来理解。一旦写成total - x 2 * S这个等式所有原本含糊的地方都消失了。这里我建议刷题的朋友养成一个习惯拿到题先在草稿纸上用字母把条件写下来看看能不能通过移项、代入、变形变成更简单的形式再动手设计算法。很多所谓“中等题”其实考的就是这个“翻译”能力。2. “枚举右维护左”的思维框架为什么这题 O(n) 就能解2.1 先把这个框架讲明白“枚举右维护左”听起来像某种高级双指针技巧实际上它的核心思想非常朴素当问题需要在一对元素之间建立某种关系时不要用双重循环去配对而是固定其中一个元素枚举“右”把另一个元素的可能信息提前维护好维护“左”从而把配对过程从 O(n^2) 降到 O(n)。一个最经典的例子是“两数之和”给定数组和一个目标值target找两个数使它们的和等于target。暴力做法是枚举i和j双重循环优化做法是遍历一遍数组把已经见过的数字放进哈希表对于当前数字nums[i]只需要查target - nums[i]在不在哈希表里即可。这个过程就是典型的“枚举右维护左”——遍历到i时i左侧所有元素的信息都被维护好了。回到 3371 这道题虽然它并不是严格意义上的“左右位置关系”但思维模型是一样的枚举一个变量作为“基准”用辅助数据结构维护另一个变量的可选择性。2.2 如何套用到本题根据前面的数学推导我们要做的事情是枚举每个元素x把它当作可能的离群值计算target total - x如果target是偶数令y target / 2判断y是否是数组中一个不同于x的元素如果成立x就是一个合法的离群值记录最大值。在这个模型里被枚举的x就是“右”我们需要判断的候选y的集合就是“左”维护这个集合的数据结构是哈希表记录每个元素出现的频率。也就是说“枚举右维护左”在这里并不需要指针它的本质是用空间换时间把“在剩余数组中查找某个值是否存在”的操作变成O(1)查询。2.3 复杂度为什么是 O(n)整个算法只需要遍历数组一次构建频率表是O(n)枚举离群值也是O(n)每次枚举里的查表和算术运算都是O(1)。总时间复杂度O(n)空间复杂度O(n)。这里还需要注意一个细节数组中元素可能很大也可能有负数。题目给的数值范围极端情况下total - x可能超出int的表示范围所以建议用long long来存储总和以及计算过程中的中间值。我在 C 里就习惯性地把total定义成long long省得边界数据一上来就溢出。3. 完整实现与逐行拆解一份不会写错的参考代码3.1 C 实现下面是我实际提交通过的版本关键逻辑都写了注释class Solution { public: int getLargestOutlier(vectorint nums) { unordered_mapint, int freq; long long total 0; // 第一遍扫描统计频率计算总和 for (int v : nums) { freq[v]; total v; } int ans -1; // 如果不存在合法离群值返回 -1 // 枚举每个元素假设它是离群值 for (int x : nums) { long long remain total - x; // remain 必须是偶数否则 2 * S remain 无整数解 if (remain % 2 ! 0) continue; int y remain / 2; // 可能的和元素值 // y 必须出现在数组里 if (freq.find(y) freq.end()) continue; // 如果 y 和 x 数值相同必须保证数组里至少有两个这样的值 // 因为和元素与离群值在位置上必须是两个不同的元素 if (y x freq[y] 2) continue; ans max(ans, x); } return ans; } };最容易被忽略的是最后那个if (y x freq[y] 2)。如果没有这个判断像[1, 1, 1]这样的用例就会出问题。逐个推一下[1, 1, 1]total 3枚举第一个1作为离群值remain 2y 1y在频率表里且频率为 3但当前枚举的x 1频率至少为 2说明数组中确实存在另一个1可以作为和元素因此离群值1合法。再看[1, 2, 3]total 6枚举x 1remain 5奇数跳过枚举x 2remain 4y 2但y x且freq[2] 1不合法枚举x 3remain 3奇数跳过返回-1符合预期。3.2 Python 实现Python 版本逻辑一模一样用Counter会非常简洁from collections import Counter class Solution: def getLargestOutlier(self, nums: List[int]) - int: freq Counter(nums) total sum(nums) ans -1 for x in nums: remain total - x if remain % 2 ! 0: continue y remain // 2 if y not in freq: continue if y x and freq[y] 2: continue ans max(ans, x) return ans两个版本的核心都是枚举离群值 → 计算目标和元素值 → 用频率表判断合法性。代码量很少但每一步都有明确的数学依据不容易写错。3.3 为什么用频率表而不是 set 或排序你可能会有疑问判断“某个值是否存在”用set不就行了吗为什么非要频率表因为存在“离群值和和元素值相同”的情况。如果用set[1, 2, 1]这种用例中枚举x 1时y 1在set里存在我们无法判断这个1是不是就是当前枚举的这个位置。万一数组只有一个1它既当离群值又当和元素就乱套了。频率表记录的是“值出现了几次”所以能精确回答除了当前正在枚举的这个元素数组中是否还有另一个相同的值可以作为和元素。这是set做不到的。那排序能不能做可以排序之后配合某种查找方式也能判断但没必要。排序本身是O(n log n)而哈希表方案是严格的O(n)。在面试或者周赛这种场景下哈希表方案更直接、更好解释。我把三种方案的对比整理了一下方案时间复杂度空间复杂度能否处理 y x 的情况评价双重循环暴力O(n^2)O(1)容易处理数据量一大就超时排序 二分查找O(n log n)O(1)需要额外处理频率可行但没必要哈希表计数O(n)O(n)频率判断即可最优推荐4. 真正容易翻车的边界频率、奇偶性、负值这道题提交时真正会卡住人的不是主逻辑而是几个边界细节。我在测试和实际提交过程中至少踩过三个坑下面一个一个说。4.1 离群值与和元素值相同的情况先看一个最简单的用例[1, 1, 2]。total 4枚举x 1remain 3奇数跳过枚举x 1第二个同样跳过枚举x 2remain 2y 1y ! x频率表里1出现两次合法答案是2。这个用例没什么问题。真正容易出错的是[1, 1, 1]这种所有元素都相同的情况。如果不加y x freq[y] 2这个条件第一次枚举x 1时就会把1当成合法离群值这本身没问题但如果数组是[1, 2, 2]这样只枚举到x 2而数组里只有两个2其中一个被当成离群值后另一个确实可以作为和元素这是合法的。关键在于我们要找的“和元素”和“离群值”在位置上必须是两个不同的元素值相同没关系但位置不能重合。频率表能直接体现这一点。我建议在写代码时把这段判断单独拎出来写成注释因为它是整个算法里最容易在复查时被误删的逻辑。4.2total - x为奇数时的处理题目里的元素都是整数所以2 * S必然是偶数。也就是说如果total - x是奇数那么x不可能成为合法离群值直接跳过即可。这个判断放在循环体的最前面能省掉后面一半的计算量也让逻辑更清晰。举个例子数组[1, 2, 3]total 6枚举x 1remain 5奇数跳过枚举x 3remain 3奇数跳过。如果没有这个判断remain / 2在 C 里做整数除法会得到错误结果比如5 / 2 2而实际上2 * 2 4 ! 5就会误判。Python 的/会得到浮点数又可能引入精度问题所以这个奇偶判断不是可选项而是必选项。4.3 负数元素带来的干扰数组允许负数比如[-2, -2, 2]。这时候total -2。让我推一遍枚举x -2remain 0y 00不在数组里跳过枚举x -2第二个同样跳过枚举x 2remain -4y -2频率表里有且y ! x合法答案是2。能够正常工作。但有两点要提醒初学者第一remain和y都可能是负数所以freq.find(y)查的是负数值的频率这个没问题因为哈希表支持任意整数值作为键。第二初始化ans -1可能会导致一个语义上的误会如果合法离群值恰好也是-1返回值依然是-1和“不存在”混淆了。不过按照题意元素范围里完全可能出现-1这时候更稳妥的做法是把ans初始化为INT_MIN然后用一个bool变量记录是否找到了合法值。我实际写的时候更习惯这样int ans INT_MIN; bool found false; for (int x : nums) { // ... 判断逻辑 if (合法) { ans max(ans, x); found true; } } return found ? ans : -1;这样就不会被“离群值恰好是 -1”这种巧合干扰。虽然力扣这题的官方用例里似乎没有针对这个点的极端测试但面试时写成这样更严谨。4.4 极端小规模用例验证当n 3时整个数组形如[S, S, x]因为此时只有一个特殊数字它的总和S等于它自身和元素的值也必须是S。来几个用例[2, 2, 1]total 5枚举x 1remain 4y 2合法答案1[0, 0, 0]total 0枚举x 0remain 0y 0频率是 3y x但频率大于等于 2合法答案0[1, 2, 4]total 7枚举x 1remain 6y 3不存在枚举x 2remain 5奇数枚举x 4remain 3奇数返回-1。这两个用例能过说明逻辑基本闭环。5. 从这题延伸出去同类变形与刷题/面试的发挥点5.1 如果题目换个问法代码怎么改这题常见的变体有几种找最小离群值把ans max(ans, x)改成ans min(ans, x)同时注意初始化值为INT_MAX。统计合法离群值的个数把ans改成计数器每次合法就cnt。要求离群值必须大于等于某个阈值在更新答案前再加一个判断。这些改动都不影响核心算法因为枚举和判断的逻辑完全不变。这也说明理解“等式”比背代码重要得多。5.2 这类“等式 枚举一个变量 查另一个变量”的问题模型3371 不是唯一用这种模型解决的题。我随便就能举出几个两数之和枚举nums[i]查target - nums[i]是否在哈希表里连续子数组和为 k枚举右端点维护前缀和的哈希表查prefix_sum - k出现过几次分割等和子集先求总和的一半作为目标值再转化为 0/1 背包或子集和问题。它们的共同点是用一个等式把一个“配对问题”变成“存在性查询问题”。而“枚举右维护左”这个框架就是这套思维的概括。顺带说一句很多看起来需要“贪心”、“二分”、“排序”的题目其实底层也可以用这个模型去推导。比如某些贪心题先排序之后枚举一个端点、用某种数据结构维护另一侧的最优值本质上也是“枚举右维护左”。学会这套框架之后后面遇到新题会少吃很多苦头。5.3 面试时如何一步步引导出这个解法如果面试官抛出这道题我会建议按这样的顺序来沟通先复述题目确认“特殊数字”“和元素”“离群值”这三个概念在纸上写出total 2*S x这个等式并向面试官解释“移项变形”的思路提出最直观的暴力解法枚举离群值再枚举和元素O(n^2)指出可以用频率表把查找优化到O(1)重点讨论y x时的频率判断以及total - x为奇数时的跳过逻辑。整个过程不需要背代码只需要把等式讲清楚代码自然就出来了。我个人在实际刷题中的体会是这道题最大的价值不是考你会不会哈希表而是考你有没有“先把题目翻译成公式”的意识。很多人卡住不是因为不会哈希表而是因为从头到尾都在用自然语言理解条件没有迈出“移项变形”这一步。最后再分享一个小技巧如果你在草稿纸上把total 2*S x写出来然后再去枚举整个思路会顺很多。反过来如果你先写了代码再想为什么大概率会在边界条件上反复试探。先公式后代码能省一半调试时间。