DeepSeek LintCode 3706 · 满足条件的数对的数量 public long countValidPairs(int[] nums1, int[] nums2, int dif

这个问题是 LintCode 3706 “满足条件的数对的数量”要求统计满足nums1[i] - nums1[j] nums2[i] - nums2[j] diff其中i j的数对(i, j)的数量。问题理解给定两个数组nums1和nums2以及一个整数diff求满足以下条件的数对(i, j)的数量i jnums1[i] - nums1[j] nums2[i] - nums2[j] diff这个不等式可以变形为nums1[i] - nums2[i] nums1[j] - nums2[j] diff令a[i] nums1[i] - nums2[i]那么条件变为a[i] a[j] diff即a[i] - diff a[j]对于每个j需要统计所有i j且a[i] - diff a[j]的数量。关键思路这是一个典型的顺序统计 二分查找问题预处理得到数组a其中a[i] nums1[i] - nums2[i]遍历j从 0 到 n-1对于当前j需要统计已处理元素中满足a[i] a[j] diff的数量将a[j]插入到有序结构中累加统计结果由于i j的限制我们需要在遍历时动态维护已遍历元素的有序集合并支持插入元素查询小于等于某个值的元素个数方法一离散化 树状数组Fenwick Tree时间复杂度 O(n log n)空间复杂度 O(n)importjava.util.*;publicclassSolution{publiclongcountValidPairs(int[]nums1,int[]nums2,intdiff){intnnums1.length;// 1. 计算 a[i]long[]anewlong[n];for(inti0;in;i){a[i](long)nums1[i]-nums2[i];}// 2. 离散化所有可能的值a[i] 和 a[i] diffTreeSetLongsetnewTreeSet();for(longval:a){set.add(val);set.add(valdiff);}ListLongsortedValsnewArrayList(set);MapLong,IntegerindexMapnewHashMap();for(inti0;isortedVals.size();i){indexMap.put(sortedVals.get(i),i1);// 树状数组从1开始}// 3. 树状数组FenwickTreebitnewFenwickTree(sortedVals.size());longans0;// 4. 遍历 jfor(intj0;jn;j){// 查询所有 i j 且 a[i] a[j] diff 的数量intidxindexMap.get(a[j]diff);ansbit.query(idx);// 将当前 a[j] 插入intposindexMap.get(a[j]);bit.update(pos,1);}returnans;}classFenwickTree{int[]tree;intsize;FenwickTree(intn){sizen;treenewint[n2];}voidupdate(intidx,intdelta){while(idxsize){tree[idx]delta;idxidx-idx;}}intquery(intidx){intsum0;while(idx0){sumtree[idx];idx-idx-idx;}returnsum;}}}方法二归并排序分治法利用归并排序的过程统计满足条件的逆序对数量时间复杂度 O(n log n)publicclassSolution{publiclongcountValidPairs(int[]nums1,int[]nums2,intdiff){intnnums1.length;long[]anewlong[n];for(inti0;in;i){a[i](long)nums1[i]-nums2[i];}returnmergeSortAndCount(a,0,n-1,diff);}privatelongmergeSortAndCount(long[]a,intleft,intright,intdiff){if(leftright)return0;intmidleft(right-left)/2;longcountmergeSortAndCount(a,left,mid,diff)mergeSortAndCount(a,mid1,right,diff);// 统计跨左右区间满足条件的对数// 对于右区间的每个元素 a[j]统计左区间中 a[i] a[j] diff 的数量intileft;for(intjmid1;jright;j){while(imida[i]a[j]diff){i;}count(i-left);}// 归并排序long[]tempnewlong[right-left1];intpleft,qmid1,k0;while(pmidqright){if(a[p]a[q]){temp[k]a[p];}else{temp[k]a[q];}}while(pmid)temp[k]a[p];while(qright)temp[k]a[q];System.arraycopy(temp,0,a,left,temp.length);returncount;}}方法三平衡二叉搜索树TreeMap直接使用 Java 的TreeMap实现代码简洁但效率稍低TreeMap 操作 O(log n) 但常数较大importjava.util.*;publicclassSolution{publiclongcountValidPairs(int[]nums1,int[]nums2,intdiff){intnnums1.length;long[]anewlong[n];for(inti0;in;i){a[i](long)nums1[i]-nums2[i];}// 使用 TreeMap 存储已遍历元素的频次TreeMapLong,IntegercountMapnewTreeMap();longans0;for(intj0;jn;j){// 查询所有 a[j] diff 的元素数量longtargeta[j]diff;// 使用 headMap 获取所有 target 的键值对SortedMapLong,IntegerheadMapcountMap.headMap(target,true);for(intcnt:headMap.values()){anscnt;}// 插入当前元素countMap.put(a[j],countMap.getOrDefault(a[j],0)1);}returnans;}}复杂度分析方法时间复杂度空间复杂度树状数组O(n log n)O(n)归并排序O(n log n)O(n)TreeMapO(n log n)O(n)示例验证输入: nums1 [1,2,3,4], nums2 [2,3,4,5], diff 1计算 a [-1, -1, -1, -1]遍历过程j0: 查询 -110 的数量 0插入 -1j1: 查询 0 的数量 1插入 -1j2: 查询 0 的数量 2插入 -1j3: 查询 0 的数量 3插入 -1结果 0123 6 ✅总结这道题的关键在于将原不等式转化为a[i] a[j] diff的形式其中a[i] nums1[i] - nums2[i]然后使用顺序统计 二分查找的思路解决。树状数组方法需要离散化归并排序方法更简洁且无需离散化推荐使用。