'2025/04/19'에 해당되는 글 1건

Leetcode Problem:

• Count the Number of Fair Pairs

Summary

• The problem is to count the number of fair pairs in a given integer array, where a pair is considered fair if the sum of its elements falls within a specified range.

Approach

• The approach used is to first sort the array and then use a binary search approach to find the number of pairs that satisfy the condition
• The binary search is performed in two separate ranges, one for the lower bound and one for the upper bound, to ensure that the sum of each pair falls within the specified range.

Complexity

• O(n log n) due to the sorting operation, where n is the size of the array.

Explanation

• The code sorts the array and then iterates over each element
• For each element, it uses binary search to find the number of pairs that satisfy the condition
• The binary search is performed in two separate ranges, one for the lower bound and one for the upper bound
• The results of the binary searches are then combined to calculate the total number of fair pairs.

Solution Code:

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