class Solution {
public:
long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int diff) {
}
};
2426. 满足不等式的数对数目
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两个数组的大小都为 n ，同时给你一个整数 diff ，统计满足以下条件的 数对 (i, j) ：
0 <= i < j <= n - 1 且nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff.请你返回满足条件的 数对数目 。
示例 1：
输入：nums1 = [3,2,5], nums2 = [2,2,1], diff = 1 输出：3 解释： 总共有 3 个满足条件的数对： 1. i = 0, j = 1：3 - 2 <= 2 - 2 + 1 。因为 i < j 且 1 <= 1 ，这个数对满足条件。 2. i = 0, j = 2：3 - 5 <= 2 - 1 + 1 。因为 i < j 且 -2 <= 2 ，这个数对满足条件。 3. i = 1, j = 2：2 - 5 <= 2 - 1 + 1 。因为 i < j 且 -3 <= 2 ，这个数对满足条件。 所以，我们返回 3 。
示例 2：
输入：nums1 = [3,-1], nums2 = [-2,2], diff = -1 输出：0 解释： 没有满足条件的任何数对，所以我们返回 0 。
提示：
n == nums1.length == nums2.length2 <= n <= 105-104 <= nums1[i], nums2[i] <= 104-104 <= diff <= 104原站题解
golang 解法, 执行用时: 144 ms, 内存消耗: 9.5 MB, 提交时间: 2023-09-18 17:30:47
func numberOfPairs(a, nums2 []int, diff int) (ans int64) {
for i, x := range nums2 {
a[i] -= x
}
// 配合下面的二分，离散化
set := map[int]struct{}{}
for _, v := range a {
set[v] = struct{}{}
}
b := make(sort.IntSlice, 0, len(set))
for x := range set {
b = append(b, x)
}
sort.Ints(b)
t := make(BIT, len(a)+1)
for _, x := range a {
ans += int64(t.query(b.Search(x + diff + 1)))
t.add(b.Search(x) + 1)
}
return
}
type BIT []int
func (t BIT) add(x int) {
for x < len(t) {
t[x]++
x += x & -x
}
}
func (t BIT) query(x int) (res int) {
for x > 0 {
res += t[x]
x &= x - 1
}
return
}
java 解法, 执行用时: 74 ms, 内存消耗: 56.3 MB, 提交时间: 2023-09-18 17:30:26
class Solution {
public long numberOfPairs(int[] a, int[] nums2, int diff) {
var n = a.length;
for (var i = 0; i < n; ++i)
a[i] -= nums2[i];
var b = Arrays.stream(a).distinct().sorted().toArray(); // 配合下面的二分，离散化
var ans = 0L;
var t = new BIT(b.length + 1);
for (var x : a) {
ans += t.query(lowerBound(b, x + diff + 1));
t.add(lowerBound(b, x) + 1);
}
return ans;
}
private int lowerBound(int[] a, int x) {
int left = 0, right = a.length;
while (left < right) {
var mid = left + (right - left) / 2;
if (a[mid] < x) left = mid + 1;
else right = mid;
}
return left;
}
}
class BIT {
private final int[] tree;
public BIT(int n) {
tree = new int[n];
}
public void add(int x) {
while (x < tree.length) {
++tree[x];
x += x & -x;
}
}
public int query(int x) {
var res = 0;
while (x > 0) {
res += tree[x];
x &= x - 1;
}
return res;
}
}
cpp 解法, 执行用时: 224 ms, 内存消耗: 77.4 MB, 提交时间: 2023-09-18 17:30:12
class BIT {
private:
vector<int> tree;
public:
BIT(int n) : tree(n) {}
void add(int x) {
while (x < tree.size()) {
++tree[x];
x += x & -x;
}
}
int query(int x) {
int res = 0;
while (x > 0) {
res += tree[x];
x &= x - 1;
}
return res;
}
};
class Solution {
public:
long long numberOfPairs(vector<int> &a, vector<int> &nums2, int diff) {
int n = a.size();
for (int i = 0; i < n; ++i)
a[i] -= nums2[i];
auto b = a;
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end()); // 配合下面的二分，离散化
long ans = 0L;
auto t = new BIT(n + 1);
for (int x : a) {
ans += t->query(upper_bound(b.begin(), b.end(), x + diff) - b.begin());
t->add(lower_bound(b.begin(), b.end(), x) - b.begin() + 1);
}
return ans;
}
};
python3 解法, 执行用时: 1084 ms, 内存消耗: 34.7 MB, 提交时间: 2023-09-18 17:29:43
# 离散化树状数组
class Solution:
def numberOfPairs(self, a: List[int], nums2: List[int], diff: int) -> int:
for i, x in enumerate(nums2):
a[i] -= x
b = sorted(set(a)) # 配合下面的二分，离散化
ans = 0
t = BIT(len(b) + 1)
for x in a:
ans += t.query(bisect_right(b, x + diff))
t.add(bisect_left(b, x) + 1)
return ans
class BIT:
def __init__(self, n):
self.tree = [0] * n
def add(self, x):
while x < len(self.tree):
self.tree[x] += 1
x += x & -x
def query(self, x):
res = 0
while x > 0:
res += self.tree[x]
x &= x - 1
return res