LeetCode 2563.统计公平数对的数目：排序 + 二分查找

【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 + nums[j] <= upper
  

 
示例 1：

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

复制代码

示例 2：

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

复制代码

 
提示：

• 1 <= nums.length <= 105
  
• nums.length == n
  
• -109 <= nums <= 109
  
• -109 <= lower <= upper <= 109
  

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

要找的是值在肯定范围内的                                   n                         u                         m                         s                         [                         i                         ]                         +                         n                         u                         m                         s                         [                         j                         ]                              nums + nums[j]                  nums+nums[j]，且加法满足互换律(                                   a                         +                         b                         =                         b                         +                         a                              a+b=b+a                  a+b=b+a)，所以查找结果和元素顺序无关。
所以只需要遍历                                   n                         u                         m                         s                              nums                  nums的下标作为                                   i                              i                  i，并在                                   i                         +                         1                              i+1                  i+1到数组末端的范围内查找                                   j                              j                  j的范围，终极累加到答案中即可。
   如何确定                                        j                                  j                     j的范围？                                        u                            p                            p                            e                            r                            _                            b                            o                            u                            n                            d                            (                            u                            p                            p                            e                            r                            −                            i                            )                            −                            l                            o                            w                            e                            r                            _                            b                            o                            u                            n                            d                            (                            l                            o                            w                            e                            r                            −                            i                            )                                  upper\_bound(upper - i) - lower\_bound(lower - i)                     upper_bound(upper−i)−lower_bound(lower−i)或                                        l                            o                            w                            e                            r                            _                            b                            o                            u                            n                            d                            (                            u                            p                            p                            e                            r                            −                            i                            +                            1                            )                            −                            l                            o                            w                            e                                       r                               b                                      o                            u                            n                            d                            (                            l                            o                            w                            e                            r                            −                            i                            )                                  lower\_bound(upper - i + 1) - lower_bound(lower - i)                     lower_bound(upper−i+1)−lowerb​ound(lower−i)均可。
  此中                                        l                            o                            w                            e                                       r                               b                                      o                            u                            n                            d                            (                            t                            )                                  lower_bound(t)                     lowerb​ound(t)黑白递减数组中第一个插入                                        t                                  t                     t后数组仍非递减的下标，                                        u                            p                            p                            e                                       r                               b                                      o                            u                            n                            d                            (                            t                            )                                  upper_bound(t)                     upperb​ound(t)黑白递减数组中末了一个插入                                        t                                  t                     t后数组仍非递减的下标。
  

• 时间复杂度                                        O                            (                            n                            log                            ⁡                            n                            )                                  O(n\log n)                     O(nlogn)，此中                                        n                            =                            l                            e                            n                            (                            n                            u                            m                            s                            )                                  n=len(nums)                     n=len(nums)
  
• 空间复杂度                                        O                            (                            log                            ⁡                            n                            )                                  O(\log n)                     O(logn)
  

AC代码

C++

1. /*
2. * @Author: LetMeFly
3. * @Date: 2025-04-19 15:51:42
4. * @LastEditors: LetMeFly.xyz
5. * @LastEditTime: 2025-04-19 16:12:44
6. */
7. /*
8. l: first j 满足 nums[j] + nums[i] >= lower | nums[j] >= lower - nums[i]
9. r: last  j 满足 nums[j] + nums[i] <= upper | nums[j] <= upper - nums[i]
11. l: lower_bound(lower - nums[i])
12. r: upper_bound(upper - nums[i])
13. */
14. typedef long long ll;
15. class Solution {
16. public:
17.     long long countFairPairs(vector<int>& nums, int lower, int upper) {
18.         sort(nums.begin(), nums.end());
19.         ll ans = 0;
20.         for (int i = 0; i < nums.size(); i++) {
21.             ans += upper_bound(nums.begin() + i + 1, nums.end(), upper - nums[i]) - lower_bound(nums.begin() + i + 1, nums.end(), lower - nums[i]);
22.             // 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;
23.         }
24.         return ans;
25.     }
26. };

复制代码

Python

1. '''
2. Author: LetMeFly
3. Date: 2025-04-19 16:13:37
4. LastEditors: LetMeFly.xyz
5. LastEditTime: 2025-04-19 16:23:38
6. '''
7. from typing import List
8. from bisect import bisect_left, bisect_right
11. class Solution:
12.     def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
13.         nums.sort()
14.         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

1. /*
2. * @Author: LetMeFly
3. * @Date: 2025-04-19 16:24:08
4. * @LastEditors: LetMeFly.xyz
5. * @LastEditTime: 2025-04-19 16:37:36
6. */
7. import java.util.Arrays;
9. class Solution {
10.     private int search(int[] nums, int x, int l) {  // search [l, len(nums)) 范围内第一个大于等于x的下标
11.         int r = nums.length;
12.         while (l < r) {
13.             int mid = (l + r) >> 1;
14.             if (nums[mid] >= x) {
15.                 r = mid;
16.             } else {
17.                 l = mid + 1;
18.             }
19.         }
20.         return l;
21.     }
22.     public long countFairPairs(int[] nums, int lower, int upper) {
23.         Arrays.sort(nums);
24.         long ans = 0;
25.         for (int i = 0; i < nums.length; i++) {
26.             ans += search(nums, upper - nums[i] + 1, i + 1) - search(nums, lower - nums[i], i + 1);
27.         }
28.         return ans;
29.     }
30. }

复制代码

Go

1. /*
2. * @Author: LetMeFly
3. * @Date: 2025-04-19 16:24:24
4. * @LastEditors: LetMeFly.xyz
5. * @LastEditTime: 2025-04-19 16:43:06
6. */
7. package main
8. import (
9.     "sort"
10. )
12. func countFairPairs(nums []int, lower int, upper int) (ans int64) {
13.     sort.Ints(nums)
14.     for i, v := range nums {
15.         l := sort.Search(len(nums), func(x int) bool {return x > i && nums[x] >= lower - v})
16.         r := sort.Search(len(nums), func(x int) bool {return x > i && nums[x] >= upper - v + 1})
17.         ans += int64(r - l)
18.     }
19.     return
20. }

复制代码

  同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
  千篇源码题解已开源

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。