leetcode

Leetcode problem solutions
git clone https://git.sinitax.com/sinitax/leetcode
Log | Files | Refs | sfeed.txt

2563-count-the-number-of-fair-pairs.rs (2262B)

      1/// 2563. Count the Number of Fair Pairs (Medium)
      2///
      3/// Given a *0-indexed* integer array nums of size n and two integers lower and
      4/// upper, return the number of fair pairs.
      5///
      6/// A pair (i, j) is fair if:
      7///
      8///   * 0 <= i < j < n, and
      9///   * lower <= nums[i] + nums[j] <= upper
     10///
     11/// *Example 1:*
     12///
     13///   *Input:* nums = [0,1,7,4,4,5], lower = 3, upper = 6
     14///   *Output:* 6
     15///   *Explanation:* There are 6 fair pairs: (0,3), (0,4), (0,5), (1,3), (1,4),
     16///   and (1,5).
     17///
     18/// *Example 2:*
     19///
     20///   *Input:* nums = [1,7,9,2,5], lower = 11, upper = 11
     21///   *Output:* 1
     22///   *Explanation:* There is a single fair pair: (2,3).
     23///
     24/// *Constraints:*
     25///
     26///   * 1 <= nums.length <= 105
     27///   * nums.length == n
     28///   * -109 <= nums[i] <= 109
     29///   * -109 <= lower <= upper <= 109
     30///
     31use leetcode::*;
     32use std::cmp::{self, Ordering};
     33
     34struct Solution {}
     35
     36impl Solution {
     37    pub fn count_fair_pairs(mut nums: Vec<i32>, lower: i32, upper: i32) -> i64 {
     38        nums.sort_unstable();
     39        let mut left = 0usize;
     40        let mut right = nums.len() - 1;
     41        let mut answer = 0usize;
     42        while left < right {
     43            if nums[left] + nums[right] < lower {
     44                left += 1;
     45            } else if nums[left] + nums[right] > upper {
     46                right -= 1;
     47            } else {
     48                let start = nums[left..right]
     49                    .binary_search_by(|element| match element.cmp(&(lower - nums[left])) {
     50                        Ordering::Equal => Ordering::Greater,
     51                        ord => ord,
     52                    })
     53                    .unwrap_err();
     54                let start = left + cmp::max(1, start);
     55                answer += right - start + 1;
     56                left += 1;
     57            }
     58        }
     59        answer as i64
     60    }
     61}
     62
     63pub fn main() {
     64    println!(
     65        "{:?}",
     66        Solution::count_fair_pairs(arg_into(1), arg_into(2), arg_into(3))
     67    )
     68}
     69
     70#[cfg(test)]
     71mod tests {
     72    use crate::Solution;
     73    use leetcode::vi;
     74
     75    #[test]
     76    fn test() {
     77        assert_eq!(Solution::count_fair_pairs(vi("[0,1,7,4,4,5]"), 3, 6), 6);
     78        assert_eq!(Solution::count_fair_pairs(vi("[1,7,9,2,5]"), 11, 11), 1);
     79        assert_eq!(Solution::count_fair_pairs(vi("[0,0,0,0,0,0]"), 0, 0), 15);
     80    }
     81}