2563. Count the Number of Fair Pairs

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
    int findFirstGreat(vector<int> & nums, int l, int r, int target)
    {
        while(l <= r){
            int mid = l + (r-l)/2;
            int eval = nums[mid];
            if(eval <  target ) l = mid+1;
            else r = mid-1;
        }
        return l;
    }
    int findFirstGreatThan(vector<int> & nums, int l, int r, int target)
    {
        while(l < r){
            int mid = l + (r-l)/2;
            int eval = nums[mid];
            if(eval <=  target ) l = mid+1;
            else r = mid-1;
        }
        return l;
    }
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        int n = nums.size();
        long long count = 0;
        // binary search
        sort(nums.begin(), nums.end());
        for(int i=0;i<n-1;++i)
        {
            int s = lower - nums[i], t = upper - nums[i];
            // find the first greater and equal than lower and upper;
            int a = findFirstGreat(nums, i+1, n-1, s);
            int b = findFirstGreatThan(nums, i+1, n -1 , t);

            if( b >= 0 && a >= 0 && b < n && a < n){
                if(nums[a] >= s && nums[b]  <= t) {
                    count += (b-a+1);
                    cout<<(b-a+1)<<endl;
                }
                else if(nums[a] >= s && nums[b-1] <=t){
                    count += b-a;
                    cout<<b-a<<endl;
                }
            }

        }
        return count;
        
        
    }
};

analysis

  • time complexity O(nlogn)
  • space complexity O(1)