2563.统计公平数对的数目

链接：2563.统计公平数对的数目
难度：Medium
标签：数组、双指针、二分查找、排序
简介：给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。

题解 1 - python

• 编辑时间：2023-02-12
• 执行用时：312ms
• 内存消耗：26.7MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
  def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
      nums.sort()
      res = 0
      l, r, n = 0, 0, len(nums)
      for i in range(1, n):
          while r + 1 < i and nums[r + 1] + nums[i] <= upper:
              r += 1
          while r - 1 >= 0 and nums[r] + nums[i] > upper:
              r -= 1
          while l + 1 < i and nums[l] + nums[i] < lower:
              l += 1
          while l - 1 >= 0 and nums[l - 1] + nums[i] >= lower:
              l -= 1
          if r > l:
              res += r - l + 1
          elif r == l and nums[l] + nums[i] >= lower and nums[l] + nums[i] <= upper:
              res += 1
      return res

题解 2 - rust

• 编辑时间：2023-02-12
• 执行用时：36ms
• 内存消耗：2.2MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn count_fair_pairs(nums: Vec<i32>, lower: i32, upper: i32) -> i64 {
        let mut nums = nums;
        nums.sort();
        let mut res: i64 = 0;
        let (mut l, mut r, n): (i64, i64, usize) = (0, 0, nums.len());
        for i in 1..n {
            while r + 1 < i as i64 && nums[r as usize + 1] + nums[i] <= upper {
                r += 1
            }
            while r - 1 >= 0 && nums[r as usize] + nums[i] > upper {
                r -= 1
            }
            while l + 1 < i as i64 && nums[l as usize] + nums[i] < lower {
                l += 1
            }
            while l - 1 >= 0 && nums[l as usize - 1] + nums[i] >= lower {
                l -= 1
            }
            if r > l {
                res += (r - l + 1) as i64;
            } else if r == l && nums[l as usize] + nums[i] >= lower && nums[l as usize] + nums[i] <= upper {
                res += 1
            }
        }
        res
    }
}

题解 3 - cpp

• 编辑时间：2023-02-12
• 执行用时：124ms
• 内存消耗：52.2MB
• 编程语言：cpp
• 解法介绍：双指针。

class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        long long res = 0;
        int l = 0, r = 0, n = nums.size();
        for (int i = 1; i < n; i++) {
            while (r + 1 < i && nums[r + 1] + nums[i] <= upper) r++;
            while (r - 1 >= 0 && nums[r] + nums[i] > upper) r--;            
            while (l + 1 < i && nums[l] + nums[i] < lower) l++;
            while (l - 1 >= 0 && nums[l - 1] + nums[i] >= lower) l--;
            if (r > l) res += r - l + 1;
            else if (r == l && nums[l] + nums[i] >= lower && nums[l] + nums[i] <= upper) res += 1;  
        }
        return res;
    }
};