千问 LeetCode 2426.满足不等式的数对数目 Go实现

这道题在 Go 中的实现思路与 Java 完全一致，核心都是将不等式变形后转化为“顺序对”计数问题，然后用树状数组或归并排序求解。

下面给出两种解法的 Go 实现。

解法一：树状数组（Fenwick Tree）

func numberOfPairs(nums1 []int, nums2 []int, diff int) int64 {
n := len(nums1)
nums := make([]int, n)
for i := 0; i 0 {
sum += bit[i]
i -= i & -i
}
return sum
}

解法二：归并排序（Merge Sort）

func numberOfPairs(nums1 []int, nums2 []int, diff int) int64 {
n := len(nums1)
nums := make([]int, n)
for i := 0; i = right {
return
}
mid := left + (right-left)/2
mergeSort(left, mid)
mergeSort(mid+1, right)

// 统计跨过中点的数对
j := mid + 1
for i := left; i <= mid; i++ {
for j <= right && nums[j]+diff < nums[i] {
j++
}
ans += int64(right - j + 1)
}

// 合并两个有序数组
i, k := left, left
j = mid + 1
for i <= mid && j <= right {
if nums[i] <= nums[j] {
temp[k] = nums[i]
i++
} else {
temp[k] = nums[j]
j++
}
k++
}
for i <= mid {
temp[k] = nums[i]
i++
k++
}
for j <= right {
temp[k] = nums[j]
j++
k++
}
copy(nums[left:right+1], temp[left:right+1])
}

mergeSort(0, n-1)
return ans
}

两种解法对比
特性 树状数组 归并排序
思路 从左到右遍历，查询已遍历元素中满足条件的个数 分治思想，在合并过程中统计跨中点的数对
需要离散化 是 否
代码量 稍短 稍长
常数 较大（涉及哈希表和二分） 较小
面试推荐 思路直观，容易解释 代码优雅，无需离散化

两种解法的时间复杂度都是 O(n log n)，空间复杂度 O(n)。