企业官网建设流程全解析

LeetCode 493 这道“反转对”，是我刷分治类题目时印象很深的一道 Hard。原因很真实：第一眼看题面，感觉它就是“逆序对”的加强版，逆序对用归并排序能解，那这题把判断条件里的nums[i] > nums[j]改成nums[i] > 2 * nums[j]，分治的思路应该也差不多吧？真上手敲代码才发现，这个 2 倍关系把整个统计阶段的逻辑都带歪了——统计和合并的顺序怎么写、双指针为什么能不回退、2 * nums[j]怎么防溢出、负数场景下单调性还成不成立，每一个点都很容易翻车。这篇文章就把我反复调试后的完整思路、可运行代码、边界坑一次性讲透，适合刚接触分治计数类题目、以及想彻底吃透 493 题的读者。

1. 题面拆解：反转对和逆序对到底差在哪

1.1 题目原意与两个标准样例

先还原一下题面：给定一个整数数组nums，如果存在下标i < j，且满足nums[i] > 2 * nums[j]，那么(i, j)就是一个重要反转对，要求返回整个数组里反转对的总数。题目的 Hard 点不在于读题，而在于数据规模：nums的长度上限是 50000，元素还是 32 位有符号整数，这就意味着任何 O(n²) 的双重循环都跑不动，同时也要求我们在写乘法时考虑整数溢出。

两个标准样例可以帮你快速确认自己没理解偏：

• nums = [1,3,2,3,1]，答案是 2。手动验证就是3 > 2*1这两对，分别来自下标 1 和下标 3 对应的 3 与最后一个 1。
• nums = [2,4,3,5,1]，答案是 3。分别是 4 和 1、3 和 1、5 和 1 这三对，注意数组开头的 2 和最后一个 1 不构成反转对，因为2 > 2*1不成立，题目要求严格大于。

刚开始做这道题的人，最容易犯的错误就是把>=当成>，或者顺手把2 * nums[j]移项成nums[i] / 2 > nums[j]，结果因为整除丢精度翻车。这些细节放在第五部分专门讲。

1.2 和逆序对的三个本质差异

逆序对大家都很熟：i < j且nums[i] > nums[j]。493 题表面上只是在判断条件里乘了个 2，但下面三个差异会真正影响解法设计。

第一，判断条件带乘法，导致我们不能沿用“左半当前值大于右半当前值，则左半剩余元素全部大于右半当前值”这种经典归并统计逻辑。逆序对在合并循环里一句nums[p1] > nums[p2]就能顺手计数，反转对不行。你看，3 > 4不成立，3 > 2*4当然更不成立，可一旦左半换成更大的元素，比如 9，9 > 2*4就成立了。必须在合并前单独做一次统计，用额外指针确认每个左半元素到底对应哪些右半元素。

第二，乘法存在整数溢出风险。当nums[j]接近 int 最大值时，2 * nums[j]直接溢出成负数，原本不成立的条件会被错误判定为成立，得到完全错误的结果。C++ 里必须用(long long)参与运算，这一点在第五部分用具体数据演示。

第三，双指针单调性的证明虽然仍然成立，但涉及“函数2x单调递增”这个隐含前提。负数环境下新手容易懵，总觉得负数和负数的比较会破坏单调性，其实只要f(x)=2x是单调的，比较关系就不会反向，指针照样不回退。为什么，第三部分用实例拆开讲。

2. 暴力解为什么过不了：从 O(n²) 到有序性假设

2.1 直白双重循环的时间账

最直觉的写法就是两层循环：外层枚举i，内层枚举所有j > i，判断nums[i] > 2 * nums[j]。代码不超过十行，跑小数组完全没问题。但n = 50000时，总比较次数接近n² / 2，也就是 12.5 亿次。这个量级在普通测评环境下需要几十秒甚至更久，超时是板上钉钉的事。就算换成某些更快的语言，12.5 亿次带乘法的比较也很不稳定，所以必须降复杂度。

为什么是n² / 2而不是n²？因为j只需要枚举i后面的数，总对数正好是组合数C(n, 2)。这个组合数的增长速度决定了任何双循环方案都不可行。想通过题目，至少要做到 O(n log n) 或 O(n log² n)。

2.2 有个天真的想法：整体排序后双指针扫，行吗

有人会想，直接把整个数组排序，然后用双指针扫一遍不就行了。但这里有个致命问题：反转对要求i < j，一旦排序，元素间的原始先后关系就全部丢失了。排序后能统计的是“无序对”的数量，而不是“满足i < j的反转对”数量，结果大概率偏大。

举例说明。[2, 1, 3]里真正的反转对只有 1 对，也就是(2,1)，因为3在1的右边，下标关系不满足。如果排序成[1,2,3]，按值大小去数，2 > 2*1成立、3 > 2*1也成立，会数出 2 对，答案就错了。

所以，必须找到一个既能保留某种顺序信息、又能加速统计的框架。这时归并排序就出现了：它天然维护了区间内元素的相对顺序，同时还能在排序过程中做计数。

2.3 树状数组方案：另一条可行的路，但偏绕

也不是说只有分治能过。固定右半每个元素j，问题就变成“在j左边有多少个nums[i]满足nums[i] > 2*nums[j]”。把每个nums[i]和2*nums[j]离散化后，可以用树状数组按顺序维护、做区间查询。这种方法时间复杂度也是 O(n log n)，但要先离散化，处理负数时还得小心映射，代码和思维负担都不小。我更建议先用分治把模型理解透，因为分治统计和归并排序是一体的，不需要额外维护任何数据结构。

3. 分治的本质：归并排序如何“顺手”统计反转对

3.1 反转对的三类位置：左右内部加跨区间

假设当前要处理的区间是[left, right]，中点是mid。区间内任意一个满足i < j的反转对，下标落点只有三种可能：

• i和j都在左半[left, mid]
• i和j都在右半[mid+1, right]
• i在左半、j在右半，也就是跨区间对

分治的第一步就是把这个区间一切为二，递归处理左半和右半，让两个子区间内部的答案先算出来。剩下真正需要“合并”阶段做的事，就只有统计“跨区间对”。这一步是分治计数类题目的通用骨架，后面迁移到 315、327 题时用的还是同一套逻辑。

3.2 关键动作：先统计，后合并

这里有一个很容易理解错的地方：归并排序的递归调用结束回到当前层时，左半和右半内部已经分别有序了。我们正是要利用这个“局部有序”来快速统计跨区间对，而不是等整个区间全排好序再统计，那时候左右边界已经消失，无法分辨元素来自哪一半，跨区间信息就丢了。

所以正确的执行顺序是：递归返回后，先用双指针在左右两个有序子数组上做统计，统计完再做常规的合并操作，把两个有序数组合并成一个更大的有序数组。统计发生在合并前，而且基于“当前左右两半已有序”这个事实。形象一点说：归并排序先通过递归把无序数组慢慢拆成有序片段，再一边把有序片段拼起来，一边在拼接前清点“跨片段的账”。

3.3 双指针为什么不需要回退：单调性与前缀区间

统计跨区间对时，输入是左半L升序、右半R升序。问题是统计所有(L[i], R[k])中满足L[i] > 2*R[k]的对数。

对固定的i，随着k增大，R[k]增大，2*R[k]也增大，所以“L[i] > 2*R[k]”这条不等式会从成立变成不成立。也就是说，满足条件的k一定集中在右半的起始段，是一个连续的前缀区间[mid+1, t-1]，其中t是第一个不满足的下标。

再看i增大时会发生什么：L[i]变大，不等式左边变大，条件只会越来越容易满足，所以第一个不满足的下标t不会向左移动，它只可能向右移动或停在原地。这就是双指针不回退的理论依据。我们只需要一个j指针从mid+1开始，随着i增大持续向右扫，均摊下来每个元素被扫过常数次，统计复杂度就是 O(n)。

拿一组具体的排序后左右半区演示。假设左半是[1,3,5,7]，右半是[1,2,3,4]：

合计 6。手动验证：3 对应右半的 1；5 对应右半的 1、2；7 对应右半的 1、2、3，正好 6 对。

这里要特别强调：每个i累加的永远是当前的j - (mid+1)，而不是“j这次向右移动了多少格”。就算i增大后j一步没动，说明当前i也仍然享有前面跳过的那几个右半元素作为满足集合，同样要把区间长度累加进去。很多人在这一步想当然，只统计j新跳过的段，导致负数和大数场景下漏计数。下面第五部分还会专门验证。

4. 完整 C++ 实现与两个关键循环的衔接

4.1 可运行代码：复用临时数组的归并版本

完整代码如下，几个处理细节我会在后面逐段解释。

class Solution { public: int reversePairs(vector<int>& nums) { tmp.resize(nums.size()); return mergeSort(nums, 0, (int)nums.size() - 1); } private: vector<int> tmp; int mergeSort(vector<int>& nums, int left, int right) { if (left >= right) return 0; int mid = left + (right - left) / 2; int cnt = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right); // 阶段一：统计跨区间反转对 int j = mid + 1; for (int i = left; i <= mid; ++i) { while (j <= right && (long long)nums[i] > 2LL * nums[j]) { ++j; } cnt += j - (mid + 1); } // 阶段二：合并左右两个有序数组 int p1 = left, p2 = mid + 1, k = left; while (p1 <= mid && p2 <= right) { if (nums[p1] <= nums[p2]) { tmp[k++] = nums[p1++]; } else { tmp[k++] = nums[p2++]; } } while (p1 <= mid) tmp[k++] = nums[p1++]; while (p2 <= right) tmp[k++] = nums[p2++]; for (int t = left; t < k; ++t) { nums[t] = tmp[t]; } return cnt; } };

这个版本里，临时数组tmp只在reversePairs入口分配一次。归并时虽然各递归层同时在占用tmp，但因为每次使用的下标范围互不重叠，所以是安全的。相比每次合并都new一个 vector，内存分配次数从 O(n log n) 降到 O(1)，实测大数组性能提升很明显。

4.2 统计循环和合并循环为什么要分成两段

这可能是 493 题最容易写炸的地方。如果把统计逻辑塞进合并的while循环里，会同时遇到两个问题。

第一，两个循环的指针移动语义不同。合并循环里p1、p2是“谁小谁走”，统计循环里j是“直到不满足 2 倍关系才停”。硬合在一起，要么统计时机错乱，要么p1、p2的移动被统计逻辑干扰。第二个问题更隐蔽：合并循环一旦开始，左右两半的元素会不断交错写入tmp，数组的“左半、右半”分界在逻辑上很快就模糊了，跨区间对的身份没法判断。

所以正确姿势是：第一段用独立的j指针把跨区间反转对数量清点完，得到cnt增量；第二段再走标准归并合并。这样每个阶段职责单一，几乎不会出现算重或算漏。

4.3 关于 mid、递归边界与下标写法

mid写成left + (right - left) / 2而不是(left + right) / 2，是为了防止left + right超过 int 上限。虽然题目长度只有 50000，构造不出那种极端下标，但好习惯要养成。

递归边界是left >= right时返回 0，因为单元素或空区间里不可能存在任何反转对。tmp的下标我直接复用原数组的下标范围，也就是k从left开始，这样最后回写时用nums[t] = tmp[t]，不需要每次计算偏移量，少了一个容易引入错位的细节。

5. 边界条件、整数溢出与高频翻车点

5.1 2 * nums[j] 溢出：一个具体到让你怀疑人生的例子

先看最极端的例子。假设nums = [INT_MAX, INT_MAX - 1]，其中INT_MAX = 2147483647。原数组中唯一可能的对是(0,1)，判断2147483647 > 2 * 2147483646。右边乘积真实值是 4294967292，显然大于左边，所以正确答案应该是 0。

但如果代码写成int val = 2 * nums[j];，这个乘积在 32 位 int 里溢出为 -4，编译器会拿2147483647 > -4来做判断，结果必然为 true，最后错误地返回 1。这就是为什么统计条件必须写成(long long)nums[i] > 2LL * nums[j]，把乘法提升到 64 位后运算，才不会截断。

5.2 负数场景：双指针不回退证明依然成立

很多人遇到负数就慌。比如nums = [-5, -3, -4, -1]，递归到某一层后，左半可能是[-5, -3]，右半可能是[-4, -1]。我们来完整推一遍跨区间对：

• (-5, -4)：-5 > 2*(-4) = -8，成立
• (-5, -1)：-5 > 2*(-1) = -2，不成立
• (-3, -4)：-3 > -8，成立
• (-3, -1)：-3 > -2，不成立

所以跨区间答案是 2。用双指针走一遍：初始j指向 -4。i = -5时，-5 > -8 成立，j移到 -1；-5 > -2 不成立，j停在 -1，cnt += 1。i = -3时，j仍然指向 -1，-3 > -2 不成立，j不动，但cnt仍然 += 1。

注意第二次累加，j一步没动，cnt却从 1 变成 2。这正是上一节强调的“每个i都要累加区间长度j - (mid+1)”，而不是“只有j移动才累加”。如果把代码写成检查j的位置变化量，这个负数例子就会漏掉(-3, -4)，输出错误的 1。

为什么指针可以不动？因为 -4 对 -5 满足条件，对更大的 -3 当然也满足条件，它始终包含在当前i的满足前缀区间里，所以j不需要回退，但区间长度依然要算到每一个新的i头上。

5.3 严格大于还是大于等于：别让乘法污染判断

题目条件是nums[i] > 2 * nums[j]，等于的情况不算。比如nums = [2,1]，2 > 2不成立，答案是 0。如果写成>=，直接错。这个细节在普通逆序对里也有，但反转对因为是乘 2，2和1这种“看似刚好两倍”的用例很容易骗到人。

建议自己构造一组边值用例：数组里放[2,1]、[3,1]、[1,2]，把大于、等于、小于三种情况都覆盖到，跑一遍确认结果分别是 0、1、0，再提交。

5.4 大数组递归栈和临时数组

n=50000 时归并递归深度约为log2(50000) ≈ 16，完全不用担心爆栈。真正要注意的是递归每层都新建 vector 的写法，内存分配次数太多，大数组下会很慢。上面的代码已经把tmp提到类成员复用了，这是实战里值得养成的习惯。

另外，面试时如果要求手写，别急着上来写 merge 过程，先把“递归、统计、合并”三段的顺序和接口讲清楚，再动手。顺序讲清楚，面试官会觉得你真的理解了分治结构，而不是在背模板。

6. 从 493 起步：同族分治统计题怎么迁移

6.1 统计类分治题的通用骨架

做过 493 之后，再看其他分治计数题会轻松很多，因为它们共用同一个骨架：

1. 递归处理左半和右半，累加两个子区间内部的答案
2. 在合并前，基于“左右各自有序”的事实统计跨区间答案
3. 合并两个有序区间，还原区间有序性

第 2 步的具体判定条件因题而异，但“利用单调性 + 双指针”的手法几乎一样。比如普通逆序对只需要统计nums[i] > nums[j]；493 反转对把条件改成nums[i] > 2*nums[j]；327 区间和的个数则是对前缀和数组做归并统计，判断preSum[i] - preSum[j]是否落入[lower, upper]区间。骨架不变，变的是第 2 步的判断方式和指针移动策略。

我把几个常见变体整理成表格：

其中 315 题比较特殊，它不只要求总计数，还要把每个下标右侧更小元素的个数存进答案里。做法是在合并统计时给元素带上原始下标，统计得到的个数直接累加到ans[原始下标]上。这个场景属于“统计结果按原数组位置展开”，比 493 多一层下标绑定，但核心还是这套归并框架。

6.2 为什么优先用分治而不是树状数组

也不是说树状数组不行。493 用“离散化 + 树状数组”也能做：固定右半元素j，查询已见过的左半元素里有多少个大于2*nums[j]，再用当前下标j减去已插入的元素个数来计算。思路本身不复杂，但需要先离散化nums[i]和2*nums[j]两套数值，负数映射还要做偏移，代码和边界处理都比归并版本长。

分治版本的优势在于：它把排序和统计耦合在同一个递归结构里，排序过程天然保留了元素的相对次序，不需要额外维护“已见过的集合”，也不用离散化。从理解难度和代码稳定性上看，分治都更适合作为第一方案。它的 O(n log n) 时间复杂度也正是评分标准里期望的复杂度，面试时讲起来逻辑更顺。

6.3 练习建议：怎么用 493 带出一整类题

我的建议是不要做完 493 就着急刷下一道，先做三件事。

第一，改条件自己变式。把 2 倍改成 3 倍，重新跑一遍，体会判定条件变化对双指针逻辑的影响。第二，把输出从“总数”改成“打印出每一对反转对”，可以逼自己把下标和边界彻底搞清。第三，按表格顺序去写 315，再看 327，对比三个题在第 2 步的差异。

这样一套下来，归并排序计数模型才算真正长在自己身上。下次遇到类似题，你能一眼认出它的分治结构，而不是在暴力、树状数组、线段树之间来回试。

最后分享一个我自己的体会。493 这道题我前前后后写了三四次，前两次都挂在同一个问题上：统计循环里只在j移动时累加，负数用例一跑就少算。后来我养成了一个小习惯——任何分治统计题写完，都强制自己用一组负数数组和一组大数数组做 sanity check，比如[-5, -3, -4, -1]期望 2，[INT_MAX, INT_MAX - 1]期望 0。这两个测试成本极低，但能把双指针单调性理解和整数溢出这两类最常见问题全部暴露出来。希望这个习惯也能帮你少走弯路。