力扣2563:统计公平数对的数目

猫梦

GitHub

我想说的话

我是一个golang萌新,请来时间我的大佬不要拷打我(多给我一些意见也是可以的)

Learn More

333 字

2 分钟

力扣2563:统计公平数对的数目

2025-12-18

力扣

三指针

题目#

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

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

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

示例 1：

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

示例 2：

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

提示：

1 <= nums.length <= 105
nums.length == n
-109 <= nums[i] <= 109
-109 <= lower <= upper <= 109

思路#

个人感觉好难, 首先将原式变为lower - num[j]<= num[i] <= upper - num[j], 然后三指针, 一指针代表j, 另外两指针代表i的范围左闭右开(能很好处理00情况)。

题解#

1
func countFairPairs(nums []int, lower int, upper int) (result int64) {
2
    sort.Ints(nums)
3
    left, right := len(nums), len(nums)
4
    for k, v := range nums {             //k就是j
5
        for right > 0 && nums[right - 1] > upper - v {   //停在符合条上件的右边
6
            right--
7
        }
8
        for left > 0 && nums[left - 1] >= lower - v {    //停在符合条件上
9
            left--
10
        }
11
        result += int64(min(right, k) - min(left, k))  //从本质上来讲left和right都是i,表示i的取值范围, 因此必须满足i < j
12
    }
13
    return
14
}