What is a fair pair in this problem?

A fair pair (i, j) satisfies 0 <= i < j < n and lower <= nums[i] + nums[j] <= upper.

Why is sorting required for Count the Number of Fair Pairs?

Sorting allows binary search to find valid partner indices efficiently for each element, which reduces overall computation.

Can we use a two-pointer approach instead of binary search?

Yes, after sorting, a two-pointer method can scan the array to count fair pairs while maintaining i < j.

What is the time complexity of this solution?

Sorting takes O(n log n), and each element uses O(log n) binary searches, giving O(n log n) overall.

How does GhostInterview help avoid common pitfalls?

It provides guided binary search setup, shows correct counting rules for pairs, and prevents double counting for identical sums.

#2563

Medium

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

LeetCode 题解工作台

统计公平数对的数目

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回公平数对的数目。如果 (i, j) 数对满足以下情况，则认为它是一个公平数对： 0 ，且 lower 示例 1：输入： nums = [0,1,7,4,4,5], lower = …

数组双指针二分查找排序

题目描述

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。

如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：

0 <= i < j < n，且
lower <= nums[i] + nums[j] <= upper

示例 1：

输入：nums = [0,1,7,4,4,5], lower = 3, upper = 6
输出：6
解释：共计 6 个公平数对：(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) 。

示例 2：

输入：nums = [1,7,9,2,5], lower = 11, upper = 11
输出：1
解释：只有单个公平数对：(2,3) 。

提示：

1 <= nums.length <= 10⁵
nums.length == n
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= lower <= upper <= 10⁹

lightbulb

解题思路

方法一：排序 + 二分查找

我们先对数组 nums 按照升序排序，然后枚举 nums[i]，对于每个 nums[i]，我们通过二分查找找到 nums[j] 的下界 j，即第一个满足 nums[j] >= lower - nums[i] 的下标，然后再通过二分查找找到 nums[k] 的下界 k，即第一个满足 nums[k] >= upper - nums[i] + 1 的下标，那么 [j, k) 即为 nums[j] 满足 lower <= nums[i] + nums[j] <= upper 的下标范围，这些下标对应的 nums[j] 的个数即为 k - j，将其累加到答案中即可。注意 $j \gt i$ 。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数组 nums 的长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        nums.sort()
        ans = 0
        for i, x in enumerate(nums):
            j = bisect_left(nums, lower - x, lo=i + 1)
            k = bisect_left(nums, upper - x + 1, lo=i + 1)
            ans += k - j
        return ans

speed

复杂度分析

指标	值
时间	O(n \log n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Sorting the array is likely expected before counting pairs.
question_mark
Look for using binary search to find the lower and upper sum bounds efficiently.
question_mark
Handling edge cases where multiple elements produce the same sum is important.

warning

常见陷阱

外企场景

error
Failing to sort nums first, which breaks binary search assumptions.
error
Incorrectly counting pairs when i >= j or double counting identical sums.
error
Ignoring the constraints leading to solutions that exceed time limits for large n.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count fair pairs where nums[i]*nums[j] falls within a range instead of sum.
arrow_right_alt
Find fair pairs allowing i <= j instead of i < j, adjusting counting logic.
arrow_right_alt
Return the actual list of fair pairs instead of just the count.

help

常见问题

外企场景

继续练习

#2576 求出最多标记下标 #2332 坐上公交的最晚时间 #2824 统计和小于目标的下标对数目