【LetMeFly】2563.統計公平數對的數目：排序 + 二分查找

力扣題目鏈接：https://leetcode.cn/problems/count-the-number-of-fair-pairs/

給你一個下標從 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 <= 105
• nums.length == n
• -109?<= nums[i] <= 109
• -109?<= lower <= upper <= 109

解題方法：排序 + 二分查找

要找的是值在一定范圍內的$nums[i]+nums[j]$，且加法滿足交換律($a+b=b+a$)，所以查找結果和元素順序無關。

所以只需要遍歷$nums$的下標作為$i$，并在$i+1$到數組末尾的范圍內查找$j$的范圍，最終累加到答案中即可。

如何確定$j$的范圍？$upper\_bound(upper?i)?lower\_bound(lower?i)$或$lower\_bound(upper?i+1)?lowe{r}_{b}ound(lower?i)$均可。

其中$lowe{r}_{b}ound(t)$是非遞減數組中第一個插入$t$后數組仍非遞減的下標，$uppe{r}_{b}ound(t)$是非遞減數組中最后一個插入$t$后數組仍非遞減的下標。

• 時間復雜度$O(n\log n)$，其中$n=len(nums)$
• 空間復雜度$O(\log n)$

AC代碼

C++

/** @Author: LetMeFly* @Date: 2025-04-19 15:51:42* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-04-19 16:12:44*/
/*
l: first j 滿足 nums[j] + nums[i] >= lower | nums[j] >= lower - nums[i]
r: last  j 滿足 nums[j] + nums[i] <= upper | nums[j] <= upper - nums[i]l: lower_bound(lower - nums[i])
r: upper_bound(upper - nums[i])
*/
typedef long long ll;
class Solution {
public:long long countFairPairs(vector<int>& nums, int lower, int upper) {sort(nums.begin(), nums.end());ll ans = 0;for (int i = 0; i < nums.size(); i++) {ans += upper_bound(nums.begin() + i + 1, nums.end(), upper - nums[i]) - lower_bound(nums.begin() + i + 1, nums.end(), lower - nums[i]);// cout << i << ": " << i << "[" << lower_bound(nums.begin() + i + 1, nums.end(), lower - nums[i]) - nums.begin() << ", " << upper_bound(nums.begin() + i + 1, nums.end(), upper - nums[i]) - nums.begin() << ')' << endl;}return ans;}
};

Python

'''
Author: LetMeFly
Date: 2025-04-19 16:13:37
LastEditors: LetMeFly.xyz
LastEditTime: 2025-04-19 16:23:38
'''
from typing import List
from bisect import bisect_left, bisect_rightclass Solution:def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:nums.sort()return sum(bisect_right(nums, upper - nums[i], i + 1) - bisect_left(nums, lower - nums[i], i + 1) for i in range(len(nums)))

Java

/** @Author: LetMeFly* @Date: 2025-04-19 16:24:08* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-04-19 16:37:36*/
import java.util.Arrays;class Solution {private int search(int[] nums, int x, int l) {  // search [l, len(nums)) 范圍內第一個大于等于x的下標int r = nums.length;while (l < r) {int mid = (l + r) >> 1;if (nums[mid] >= x) {r = mid;} else {l = mid + 1;}}return l;}public long countFairPairs(int[] nums, int lower, int upper) {Arrays.sort(nums);long ans = 0;for (int i = 0; i < nums.length; i++) {ans += search(nums, upper - nums[i] + 1, i + 1) - search(nums, lower - nums[i], i + 1);}return ans;}
}

Go

/** @Author: LetMeFly* @Date: 2025-04-19 16:24:24* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-04-19 16:43:06*/
package main
import ("sort"
)func countFairPairs(nums []int, lower int, upper int) (ans int64) {sort.Ints(nums)for i, v := range nums {l := sort.Search(len(nums), func(x int) bool {return x > i && nums[x] >= lower - v})r := sort.Search(len(nums), func(x int) bool {return x > i && nums[x] >= upper - v + 1})ans += int64(r - l)}return
}

同步發文于CSDN和我的個人博客，原創不易，轉載經作者同意后請附上原文鏈接哦~

千篇源碼題解已開源