LeetCode 493. 翻转对（Reverse Pairs） 是一道经典的 分治 + 归并排序变种 题目，也可以用 树状数组（Fenwick Tree） 或 线段树 解决。这里我们重点讲解 归并排序解法（最常用、效率高、代码清晰）。

📌 题目要求

给定一个数组 nums，如果 i 2 * nums[j]，则 (i, j) 是一个翻转对。

返回数组中翻转对的总数。

示例：
nums = [1,3,2,3,1] → 翻转对有 (1,4), (3,4) → 返回 2
nums = [2,4,3,5,1] → 返回 3（(0,4), (1,4), (2,4)）

约束：-2^31 2 * nums[j]

💡 高效统计方法：

由于左右都升序，对于每个 j，满足条件的 i 是一个前缀（因为 nums[i] 越大越可能满足）。

但更高效的是：固定 i，找最小的 j 使得 nums[i] > 2 * nums[j]
→ 实际上，我们用双指针：

int count = 0;
int j = mid + 1;
for (int i = left; i 2L * nums[j]) {
j++;
}
count += (j - (mid + 1));
}

⚠️ 注意溢出！必须用 long：2L * nums[j]

但上面逻辑反了！正确做法是：

✅ 正确双指针逻辑：

int j = mid + 1;
for (int i = left; i 2 * nums[j]
while (j 2L * nums[j]) {
j++;
}
count += (j - (mid + 1));
}

❌ 错！因为当 nums[i] 增大时，满足 nums[i] > 2*nums[j] 的 j 范围不会缩小，所以 j 应该只增不减。

✅ 正确写法（j 不回退）：

int j = mid + 1;
for (int i = left; i 2L * nums[j]) {
j++;
}
// 此时，[mid+1, j-1] 都满足条件
count += (j - (mid + 1));
}

✅ 因为 nums[i] 递增，所以 j 只能向右移动（单调性）！

💻 完整 Java 实现（归并排序）

public class Solution {
public int reversePairs(int[] nums) {
if (nums == null || nums.length == 0) return 0;
return mergeSort(nums, 0, nums.length - 1);
}

private int mergeSort(int[] nums, int left, int right) {
    if (left >= right) return 0;
    
    int mid = left + (right - left) / 2;
    int count = 0;
    
    // 递归处理左右
    count += mergeSort(nums, left, mid);
    count += mergeSort(nums, mid + 1, right);
    
    // 统计跨越左右的翻转对
    count += countReversePairs(nums, left, mid, right);
    
    // 合并两个有序数组
    merge(nums, left, mid, right);
    
    return count;
}

// 统计 left~mid 和 mid+1~right 之间的翻转对
private int countReversePairs(int[] nums, int left, int mid, int right) {
    int count = 0;
    int j = mid + 1;
    
    for (int i = left; i  2L * nums[j]) {
            j++;
        }
        count += (j - (mid + 1));
    }
    return count;
}

// 标准归并
private void merge(int[] nums, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, k = 0, j = mid + 1;
    
    while (i  2L * nums[j]

双指针方向
j 从 mid+1 开始，只增不减（利用单调性，O(n) 统计）
如果每次 i 都重置 j = mid+1，会退化为 O(n²)

统计时机
必须在 merge 之前统计！因为 merge 会打乱原始索引顺序

📊 复杂度分析

时间复杂度：O(n log n)
归并排序本身 O(n log n)
每层统计翻转对 O(n)
空间复杂度：O(n)（归并临时数组）

🧪 测试用例
输入 输出 说明
[1,3,2,3,1] 2 (1,4), (3,4)

[2,4,3,5,1] 3 (0,4), (1,4), (2,4)

[5,4,3,2,1] 4 (0,4),(1,4),(2,4),(3,4)

✅ 总结
方法 是否推荐 说明
归并排序 ✅ 强烈推荐 时间 O(n log n)，代码清晰，面试首选

树状数组 ⚠️ 可选 需离散化，适合熟悉 BIT 的人

暴力 ❌ O(n²)，超时

💡 一句话口诀：
“归并排序分治搞，合并之前双指针扫；long 防溢要记牢，翻转对数轻松找。”

此解法在 LeetCode 上可稳定 AC，是标准答案 ✅