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

这道题在 Go 中的实现思路与 Java 完全一致核心都是将不等式变形后转化为“顺序对”计数问题然后用树状数组或归并排序求解。下面给出两种解法的 Go 实现。解法一树状数组Fenwick Treefunc 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 Sortfunc 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)/2mergeSort(left, mid)mergeSort(mid1, right)// 统计跨过中点的数对j : mid 1for i : left; i mid; i {for j right nums[j]diff nums[i] {j}ans int64(right - j 1)}// 合并两个有序数组i, k : left, leftj mid 1for 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]ik}for j right {temp[k] nums[j]jk}copy(nums[left:right1], temp[left:right1])}mergeSort(0, n-1)return ans}两种解法对比特性 树状数组 归并排序思路 从左到右遍历查询已遍历元素中满足条件的个数 分治思想在合并过程中统计跨中点的数对需要离散化 是 否代码量 稍短 稍长常数 较大涉及哈希表和二分 较小面试推荐 思路直观容易解释 代码优雅无需离散化两种解法的时间复杂度都是 O(n log n)空间复杂度 O(n)。