What is the best way to approach the Number of Pairs Satisfying Inequality problem?

Rearrange the inequality equation, then use binary search or a sorted array to efficiently count the valid pairs.

How do I handle large inputs in this problem?

Use binary search on the sorted array to reduce unnecessary comparisons and improve the time complexity to O(n log n).

What are common mistakes when solving this problem?

Common mistakes include neglecting the rearrangement of the inequality, using brute force approaches, and forgetting the i < j constraint.

Can the solution be extended to multiple arrays?

Yes, you can extend the approach to handle more arrays, but careful management of the inequality condition is necessary.

How does binary search optimize the solution here?

Binary search allows you to quickly determine how many valid pairs exist for each element in the sorted array, greatly improving efficiency.

#2426

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

满足不等式的数对数目

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两个数组的大小都为 n ，同时给你一个整数 diff ，统计满足以下条件的数对 (i, j) ： 0 且 nums1[i] - nums1[j] . 请你返回满足条件的数对数目。示例 1：输入： nums1 = [3,2,5…

数组二分查找分治树状数组线段树

题目描述

给你两个下标从 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.length
2 <= n <= 10⁵
-10⁴ <= nums1[i], nums2[i] <= 10⁴
-10⁴ <= diff <= 10⁴

lightbulb

解题思路

方法一：树状数组

我们将题目的不等式转换一下，得到 $nums1[i] - nums2[i] \leq nums1[j] - nums2[j] + diff$ ，因此，如果我们对两个数组对应位置的元素求差值，得到另一个数组 $nums$ ，那么题目就转换为求 $nums$ 中满足 $nums[i] \leq nums[j] + diff$ 的数对数目。

我们可以从小到大枚举 $j$ ，找出前面有多少个数满足 $nums[i] \leq nums[j] + diff$ ，这样就可以求出数对数目。我们可以使用树状数组来维护前缀和，这样就可以在 $O(\log n)$ 的时间内求出前面有多少个数满足 $nums[i] \leq nums[j] + diff$ 。

时间复杂度 $O(n \times \log n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

class BinaryIndexedTree:
    def __init__(self, n):
        self.n = n
        self.c = [0] * (n + 1)

    @staticmethod
    def lowbit(x):
        return x & -x

    def update(self, x, delta):
        while x <= self.n:
            self.c[x] += delta
            x += BinaryIndexedTree.lowbit(x)

    def query(self, x):
        s = 0
        while x:
            s += self.c[x]
            x -= BinaryIndexedTree.lowbit(x)
        return s


class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:
        tree = BinaryIndexedTree(10**5)
        ans = 0
        for a, b in zip(nums1, nums2):
            v = a - b
            ans += tree.query(v + diff + 40000)
            tree.update(v + 40000, 1)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ability to simplify a complex inequality and recognize optimization opportunities.
question_mark
Familiarity with binary search and how it can be applied to this problem.
question_mark
Experience with handling large input sizes efficiently using sorted data structures or binary search.

warning

常见陷阱

外企场景

error
Neglecting to rearrange the inequality equation properly, leading to inefficient or incorrect comparisons.
error
Attempting to solve the problem with a brute force approach, resulting in time complexity issues for large inputs.
error
Forgetting the constraint that i must be less than j, which can lead to incorrect pair counting.

swap_horiz

进阶变体

外企场景

arrow_right_alt
The problem can be extended by adding additional constraints or modifying the inequality condition to require more complex checks.
arrow_right_alt
Instead of two arrays, consider cases where you have more than two arrays and must find pairs satisfying inequalities between them.
arrow_right_alt
Introduce additional parameters to the inequality condition to further explore optimizations or extend the problem to higher-dimensional arrays.

help

常见问题

外企场景

继续练习

#2179 统计数组中好三元组数目 #1649 通过指令创建有序数组 #493 翻转对