求满足A[i]+A[j]>B[i]+B[j]（i<j）的数对数量的高效算法

首先，你当前的代码存在核心问题：单独排序A和B会破坏原数组中索引i对应的A[i]与B[i]的关联，原条件是针对同一个i的A[i]和B[i]进行计算，排序后i位置的A和B已经不是原来的配对，结果完全错误。

问题转换 #

先把原条件变形，简化问题：
原条件 A[i]+A[j] > B[i]+B[j] 可以整理为：
(A[i] - B[i]) + (A[j] - B[j]) > 0

我们定义一个新数组 C，其中 C[k] = A[k] - B[k]，问题就转化为：统计数组C中满足 C[i] + C[j] > 0 且 i < j 的数对数量。

方法1：排序+双指针法（直观高效） #

步骤：

1. 构造数组C，计算每个元素为A[i]-B[i]
2. 将C数组升序排序
3. 用双指针统计符合条件的数对：
   • 左指针left从0开始，右指针right从n-1开始
   • 对于每个right，找到最小的left使得C[left] + C[right] > 0，那么从left到right-1的所有元素与right配对都满足条件，数量为right - left
   • 然后right左移，重复上述过程

代码示例：

#include <algorithm>
#include <vector>

int countValidPairs(const std::vector<int>& A, const std::vector<int>& B) {
    int n = A.size();
    std::vector<int> C(n);
    for (int i = 0; i < n; ++i) {
        C[i] = A[i] - B[i];
    }
    std::sort(C.begin(), C.end());
    
    int count = 0;
    int left = 0;
    for (int right = n - 1; right > 0; --right) {
        // 找到第一个left使得C[left] + C[right] > 0
        while (left < right && C[left] + C[right] <= 0) {
            left++;
        }
        if (left < right) {
            count += right - left;
        } else {
            // 剩下的left都不满足，直接break
            break;
        }
    }
    return count;
}

方法2：归并排序分治法（适合理解分治思想） #

利用归并排序的过程，在合并两个有序子数组时，统计左子数组中元素与右子数组中元素满足C[i]+C[j]>0的数量，同时完成排序。这种方法时间复杂度也是O(n log n)，和双指针法效率相当。

代码示例：

#include <vector>
#include <algorithm>

int mergeAndCount(std::vector<int>& C, int left, int mid, int right) {
    std::vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    int count = 0;
    
    // 先统计左子数组和右子数组中满足C[i]+C[j]>0的数对
    while (i <= mid && j <= right) {
        if (C[i] + C[j] > 0) {
            // 左子数组中i到mid的所有元素都能和j配对
            count += mid - i + 1;
            j++;
        } else {
            i++;
        }
    }
    
    // 归并排序的合并过程
    i = left;
    j = mid + 1;
    while (i <= mid && j <= right) {
        if (C[i] <= C[j]) {
            temp[k++] = C[i++];
        } else {
            temp[k++] = C[j++];
        }
    }
    while (i <= mid) temp[k++] = C[i++];
    while (j <= right) temp[k++] = C[j++];
    
    for (int p = 0; p < temp.size(); ++p) {
        C[left + p] = temp[p];
    }
    return count;
}

int mergeSortAndCount(std::vector<int>& C, int left, int right) {
    int count = 0;
    if (left < right) {
        int mid = left + (right - left) / 2;
        count += mergeSortAndCount(C, left, mid);
        count += mergeSortAndCount(C, mid + 1, right);
        count += mergeAndCount(C, left, mid, right);
    }
    return count;
}

int countValidPairs(const std::vector<int>& A, const std::vector<int>& B) {
    int n = A.size();
    std::vector<int> C(n);
    for (int i = 0; i < n; ++i) {
        C[i] = A[i] - B[i];
    }
    return mergeSortAndCount(C, 0, n - 1);
}

时间复杂度分析 #

两种方法的时间复杂度都是O(n log n)，其中排序的时间是O(n log n)，双指针遍历或归并统计的时间是O(n)，完全满足大规模数据的处理需求，远优于暴力O(n²)的解法。

内容的提问来源于stack exchange，提问作者Daniyal