千问 LeetCode 2426.满足不等式的数对数目 public long numberOfPairs(int[] nums1, int[] nums2, int diff)
这道题的核心在于将不等式变形，转化为一个经典的“顺序对”计数问题，然后利用树状数组或归并排序高效求解。
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），供后续元素查询。
代码实现（Java）：
class 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. 离散化：收集所有可能出现的值
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
set.add(num + diff); // 因为我们要查询 <= num + diff
}
List<Integer> sorted = new ArrayList<>(set);
Collections.sort(sorted);
Map<Integer, 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] ，右半部分为 [mid+1, right] ，且它们内部已经排好序。
对于左半部分的每个元素 nums[i] ，我们需要在右半部分中找到第一个满足 nums[j] + diff < nums[i] 的元素（即不满足条件的元素），那么右半部分中从该元素到末尾的所有元素都满足条件。
使用双指针（或二分查找）来加速这个过程。
合并两个有序数组。
代码实现（Java）：
class 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)。