这道题的核心在于将不等式变形转化为一个经典的“顺序对”计数问题然后利用树状数组或归并排序高效求解。1. 核心思路不等式变形题目要求 nums1[i] - nums1[j] nums2[i] - nums2[j] diff 且 i j 。将含有 i 和 j 的项分别移到不等式两边nums1[i] - nums2[i] nums1[j] - nums2[j] diff定义一个新数组 nums 其中 nums[k] nums1[k] - nums2[k] 。那么原问题就等价于在数组 nums 中找到所有满足 i j 且 nums[i] nums[j] diff 的数对 (i, j) 的个数。2. 解法树状数组Fenwick Tree我们可以从左到右遍历数组 nums 对于当前遍历到的位置 j 我们需要统计在它之前即 i j 有多少个 nums[i] 满足 nums[i] nums[j] diff 。具体步骤离散化由于 nums[i] 和 nums[j] diff 的值范围可能很大我们需要将所有可能出现的值 nums[i] 和 nums[i] diff 进行排序和去重映射到连续的索引上。遍历与查询从左到右遍历 nums 。对于当前元素 num nums[j] 我们查询树状数组中所有小于等于 num diff 的元素个数。这相当于查询 num diff 在离散化数组中的位置然后求前缀和。将查询结果累加到答案 ans 中。将当前元素 num 插入到树状数组中在 num 对应的离散化索引位置加1供后续元素查询。代码实现Javaclass Solution {public long numberOfPairs(int[] nums1, int[] nums2, int diff) {int n nums1.length;int[] nums new int[n];for (int i 0; i n; i) {nums[i] nums1[i] - nums2[i];}// 1. 离散化收集所有可能出现的值SetInteger set new HashSet();for (int num : nums) {set.add(num);set.add(num diff); // 因为我们要查询 num diff}ListInteger sorted new ArrayList(set);Collections.sort(sorted);MapInteger, Integer map new HashMap();for (int i 0; i sorted.size(); i) {map.put(sorted.get(i), i 1); // 树状数组索引从1开始}// 2. 树状数组int m sorted.size();int[] bit new int[m 1];long ans 0;for (int num : nums) {// 查询 num diff 的元素个数int idx map.get(num diff);ans query(bit, idx);// 插入当前元素update(bit, map.get(num), 1);}return ans;}private void update(int[] bit, int i, int delta) {while (i bit.length) {bit[i] delta;i i -i;}}private int query(int[] bit, int i) {int sum 0;while (i 0) {sum bit[i];i - i -i;}return sum;}}3. 解法归并排序Merge Sort在归并排序的过程中我们可以利用左右两个子数组已经有序的特性高效地统计跨过中点的数对。具体步骤将数组 nums 递归地分成两半。先递归统计左半部分和右半部分内部的数对。统计跨过中点的数对假设左半部分为 [left, mid] 右半部分为 [mid1, right] 且它们内部已经排好序。对于左半部分的每个元素 nums[i] 我们需要在右半部分中找到第一个满足 nums[j] diff nums[i] 的元素即不满足条件的元素那么右半部分中从该元素到末尾的所有元素都满足条件。使用双指针或二分查找来加速这个过程。合并两个有序数组。代码实现Javaclass Solution {private long ans 0;private int[] temp;public long numberOfPairs(int[] nums1, int[] nums2, int diff) {int n nums1.length;int[] nums new int[n];for (int i 0; i n; i) {nums[i] nums1[i] - nums2[i];}temp new int[n];mergeSort(nums, 0, n - 1, diff);return ans;}private void mergeSort(int[] nums, int left, int right, int diff) {if (left right) return;int mid left (right - left) / 2;mergeSort(nums, left, mid, diff);mergeSort(nums, mid 1, right, diff);// 统计跨过中点的数对int j mid 1;for (int i left; i mid; i) {while (j right nums[j] diff nums[i]) {j;}ans right - j 1;}// 合并两个有序数组int i left, k left;j mid 1;while (i mid j right) {if (nums[i] nums[j]) {temp[k] nums[i];} else {temp[k] nums[j];}}while (i mid) temp[k] nums[i];while (j right) temp[k] nums[j];System.arraycopy(temp, left, nums, left, right - left 1);}}总结树状数组思路更直接适合在面试中快速写出但需要离散化处理。归并排序不需要离散化代码稍长但常数更小速度更快。两种解法的时间复杂度都是 O(n log n)空间复杂度为 O(n)。
