Medium

题目描述

给你一个下标从 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
解释：只有 1 个公平数对：(2,3) 。

提示：

  • 1 <= nums.length <= 10^5
  • nums.length == n
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= lower <= upper <= 10^9

解题思路

解题思路

方法一：双指针（推荐）

最直观的暴力解法是枚举所有数对，但时间复杂度为 O(n²)，会超时。

关键观察：如果我们对数组进行排序，那么对于固定的 nums[i]，满足条件的 nums[j] 会形成一个连续的区间。

具体步骤：

  1. 对数组进行排序
  2. 对每个位置 i，找到满足 lower <= nums[i] + nums[j] <= upper 的 j 的范围
  3. 使用双指针技术：
    • left 指针找到最小的满足 nums[i] + nums[j] >= lower 的 j
    • right 指针找到最大的满足 nums[i] + nums[j] <= upper 的 j
    • 区间 [left, right] 内的所有 j 都能与 i 组成公平数对

方法二：二分查找

对于每个 i，使用二分查找找到满足条件的 j 的上下界。但双指针方法更高效，因为指针只会单调移动。

由于排序后数组的单调性，当 i 增大时，对应的 left 和 right 边界都会向左移动，这样双指针的总移动次数不会超过 2n。

代码实现

class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        long long result = 0;
        int left = n - 1, right = n - 1;
        
        for (int i = 0; i < n - 1; i++) {
            // 找到最小的j使得nums[i] + nums[j] >= lower
            while (left > i && nums[i] + nums[left] >= lower) {
                left--;
            }
            left++;
            
            // 找到最大的j使得nums[i] + nums[j] <= upper
            while (right > i && nums[i] + nums[right] > upper) {
                right--;
            }
            
            if (left <= right) {
                result += right - left + 1;
            }
        }
        
        return result;
    }
};

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        nums.sort()
        n = len(nums)
        result = 0
        left = right = n - 1
        
        for i in range(n - 1):
            # 找到最小的j使得nums[i] + nums[j] >= lower
            while left > i and nums[i] + nums[left] >= lower:
                left -= 1
            left += 1
            
            # 找到最大的j使得nums[i] + nums[j] <= upper
            while right > i and nums[i] + nums[right] > upper:
                right -= 1
            
            if left <= right:
                result += right - left + 1
                
        return result

public class Solution {
    public long CountFairPairs(int[] nums, int lower, int upper) {
        Array.Sort(nums);
        int n = nums.Length;
        long result = 0;
        int left = n - 1, right = n - 1;
        
        for (int i = 0; i < n - 1; i++) {
            // 找到最小的j使得nums[i] + nums[j] >= lower
            while (left > i && nums[i] + nums[left] >= lower) {
                left--;
            }
            left++;
            
            // 找到最大的j使得nums[i] + nums[j] <= upper
            while (right > i && nums[i] + nums[right] > upper) {
                right--;
            }
            
            if (left <= right) {
                result += right - left + 1;
            }
        }
        
        return result;
    }
}

var countFairPairs = function(nums, lower, upper) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let result = 0;
    let left = n - 1, right = n - 1;
    
    for (let i = 0; i < n - 1; i++) {
        // 找到最小的j使得nums[i] + nums[j] >= lower
        while (left > i && nums[i] + nums[left] >= lower) {
            left--;
        }
        left++;
        
        // 找到最大的j使得nums[i] + nums[j] <= upper
        while (right > i && nums[i] + nums[right] > upper) {
            right--;
        }
        
        if (left <= right) {
            result += right - left + 1;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n log n)
空间复杂度O(1)

说明：

  • 时间复杂度：排序需要 O(n log n)，双指针遍历需要 O(n)，总体为 O(n log n)
  • 空间复杂度：只使用了常数个额外变量，为 O(1)

相关题目